#ifdef _WIN32
#define _CRT_SECURE_NO_WARNINGS 1
#endif

// 一维前缀和
/*
#include <iostream>
#include <vector>

// 一维前缀和数组dp[i]: 表示从下标1位置开始到下标位置i结束之间所有数的和
// 状态转移方程: dp[i] = dp[i-1] + v[i]
// 初始化: dp[i]{0}
// 遍历顺序: 左到右
// 查询结果: dp[r] - dp[l-1]
int main()
{
    int n = 0;
    int q = 0;

    std::cin>>n>>q; // n个数,q次查询

    std::vector<int> v(n+1,0);
    for(int i = 1; i <= n; ++i) // 获取n个数
    {
        std::cin>>v[i];
    }

    std::vector<long long> dp(n+1,0);
    for(int i = 1; i <= n; ++i) // 求一维前缀和数组
    {
        dp[i] = dp[i-1] + v[i];
    }

    int l,r;
    while(q--) // 查询逻辑
    {
        std::cin>>l>>r;
        std::cout<<dp[r]-dp[l-1]<<std::endl;
    }

    return 0;
}
*/

// 二维前缀和
/*
#include <iostream>
#include <vector>
// 二维前缀和矩阵dp[i][j]: 表示(1,1)位置到(i,j)位置所有数的和
// 状态转移方程: dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + vv[i][j]
// 初始化: dp[i][j]{0}
// 遍历顺序: 上到下左到右
// 查询结果: result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

int main()
{
    int n,m,q;
    std::cin>>n>>m>>q;

    std::vector<std::vector<long long>> vv(n+1,std::vector<long long>(m+1,0));
    auto dp = vv;
    for(int i = 1; i <= n; ++i) // 获取n*m数据
    {
        for(int j = 1; j <= m; ++j)
        {
            std::cin>>vv[i][j];
        }
    }

    for(int i = 1; i <= n; ++i) // 求二维前缀和矩阵
    {
        for(int j = 1; j <= m; ++j)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + vv[i][j];
        }
    }

    int x1,y1,x2,y2;
    while(q--) // q次查询
    {
        std::cin>>x1>>y1>>x2>>y2;
        std::cout<< dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] <<std::endl;
    }

    return 0;
}
*/

// 寻找数组的中心下标
/*
class Solution
{
public:
    // 前缀和f[i]: 表示[0,i-1]区间数的和
    // 状态转移方程: f[i] = f[i-1] + nums[i-1]
    // 初始化: f[0] = 0 表示数组最左端，那么左侧数之和视为0 ，因为在下标的左侧不存在元素。
    // 后缀和g[i]: 表示[i+1,n-1]区间数的和
    // 状态转移方程: g[i] = g[i+1] + nums[i+1]
    // 初始化: g[n-1] = 0 这一点对于中心下标位于数组最右端同样适用。
    // 如果f[i] == g[i] 其左侧所有元素相加的和等于右侧所有元素相加的和。
    int pivotIndex(vector<int>& nums)
    {
        int n = static_cast<int>(nums.size());

        auto f = nums;
        f[0] = 0;
        // 求前缀和数组
        for(int i = 1; i < n; ++i)
        {
            f[i] = f[i-1] + nums[i-1];
        }
        auto g = nums;
        g[n-1] = 0;
        // 求后缀和数组
        for(int i = n-2; i >= 0; --i)
        {
            g[i] = g[i+1] + nums[i+1];
        }

        //// 求前缀和数组 & 求后缀和数组
        //for(int i = 1; i < n; ++i)
        //{
        //    f[i] = f[i-1] + nums[i-1];
        //    g[n-i-1] = g[n-i] + nums[n-i];
        //}

        for(int i = 0; i < n; ++i)
        {
            if(g[i] == f[i]) return i;
        }

        return -1;
    }
};
*/

// 除自身以外数组的乘积 
/*
class Solution
{
public:
    // 前缀积f[i]: 表示[0,i-1]区间数的积
    // 状态转移方程: f[i] = f[i-1] * nums[i-1]
    // 初始化: f[0] = 1
    // 后缀积g[i]: 表示[i+1,n-1]区间数的积
    // 状态转移方程: g[i] = g[i+1] * nums[i+1]
    // 初始化: g[n-1] = 1
    // 返回结果: f[i] * g[i]
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = static_cast<int>(nums.size());

        auto f = nums;
        f[0] = 1;
        // 求前缀积数组
        for(int i = 1; i < n; ++i)
        {
            f[i] = f[i-1] * nums[i-1];
        }

        auto g = nums;
        g[n-1] = 1;
        // 求后缀积数组
        for(int i = n-2; i >= 0; --i)
        {
            g[i] = g[i+1] * nums[i+1];
        }

        std::vector<int> ans(n);
        // answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
        for(int i = 0; i < n; ++i)
        {
            ans[i] = (g[i] * f[i]);
        }

        return ans;
    }
};
*/

// 和为K的子数组 
/*
class Solution
{
public:
    // 设i为数组中的任意位置，⽤sum[i]表⽰[0, i]区间内所有元素的和。
    // 想知道有多少个以i为结尾的和为k的⼦数组，就要找到有多少个起始位置为x1,x2,x3...
    // 使得[x, i]区间内的所有元素的和为k那么[0, x]区间内的和是不是就是sum[i] - k了。
    // 于是问题就变成: 找到在[0, i - 1]区间内，有多少前缀和等于sum[i] - k 的即可。
    int subarraySum(vector<int>& nums, int k)
    {
        std::unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0;
        int ans = 0;
        for(auto e : nums)
        {
            sum += e;
            if(hash.find(sum - k) != hash.end())
            {
                ans+=hash[sum-k];
            }
            hash[sum]++;
        }
        return ans;
    }
};
*/

// 矩阵区域和 
/*
class Solution
{
public:
    // 二维矩阵前缀和: dp[i][j]表示(0,0)~(i,j)所有数的和
    // 状态转移方程: dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i][j]
    // 初始化: dp{0}
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int nrow = mat.size();
        int ncol = mat.back().size();

        // 创建二维矩阵前缀和
        std::vector<std::vector<int>> dp(nrow+1,std::vector<int>(ncol+1,0));
        for(int i = 1; i <= nrow; ++i)
        {
            for(int j = 1; j <= ncol; ++j)
            {
                dp[i][j] = dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        auto ans = mat;

        for(int i = 0; i < nrow; ++i)
        {
            for(int j = 0; j < ncol; ++j)
            {
                // 求出该位置对应的矩阵左上角和右下角
                int x1 = std::max(0,i - k) + 1;
                int y1 = std::max(0,j - k) + 1;
                int x2 = std::min(nrow-1,i+k) + 1;
                int y2 = std::min(ncol-1,j+k) + 1;

                ans[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }

        return ans;
    }
};
*/

// 和可被 K 整除的子数组
/*
class Solution
{
public:
    // 同余定理: (a-b)%q=k -> a%q=b%q
    int subarraysDivByK(vector<int>& nums, int k)
    {
        std::unordered_map<int,int> hash;
        hash[0 % k] = 1; // // 0 这个数的余数
        int sum = 0;
        int ans = 0;
        for(auto e : nums)
        {
            sum += e; // // 算出当前位置的前缀和
            int res = (sum%k + k)%k; //  // 修正后的余数
            if(hash.find(res) != hash.end()) // // 统计结果
            {
                ans += hash[res];
            }
            ++hash[res];
        }
        return ans;
    }
};
*/

// 罗马数字转整数
/*
class Solution
{
public:
    std::unordered_map<char,int> hash {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000},
    };
    int romanToInt(string s)
    {
        int n = static_cast<int>(s.size());
        if(n == 1) return hash[s.front()];

        int ans = hash[s[0]];
        for(int i = 1; i < n; ++i)
        {
            // std::cout<<ans<<std::endl;
            // 如果罗马数字是递减的则累加对应的数字
            if(hash[s[i-1]] >= hash[s[i]])
            {
                ans += hash[s[i]];
            }
            else // 否则进行转换
            {
                ans += hash[ s[i] ];
                ans -= 2*hash[ s[i-1] ];
            }
        }
        return ans;
    }
};
*/

// 最长公共前缀
/*
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        // 只有一个字符串直接返回该字符串
        if(strs.size() == 1) return strs.front();

        // 求行
        int nrow = strs.size();
        // 求这些字符串中最小的长度
        int minlen = strs.back().size();
        for(int i = 0; i < nrow; ++i)
        {
            minlen = std::min(minlen,(int)strs[i].size());
        }

        // 每个字符串一列一列的比较
        std::string ans;
        for(int j = 0; j < minlen; ++j)
        {
            bool flag = true;
            for(int i = 1; i < nrow; ++i)
            {
                if(strs[i-1][j] != strs[i][j]) flag = false;
            }
            if(!flag) // 如果不同则直接返回
            {
                break;
            }
            ans.push_back(strs.front()[j]);
        }

        return minlen == 0 ? "":ans;
    }
};
*/

// 字母异位词分组
/*
class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        // 字母异位词组合在一起
        std::unordered_map<std::string,std::vector<std::string>> hash;
        for(auto &str : strs)
        {
            auto t = str;
            // 如果是异位词则排序后是相同的
            std::sort(t.begin(),t.end());
            hash[t].push_back(str);
        }

        // 返回结果
        std::vector<std::vector<std::string>> vvs;
        for(auto &e : hash)
        {
            vvs.push_back(std::move(e.second));
        }
        return vvs;
    }
};
*/

// 最后一个单词的长度 
/*
class Solution {
public:
    int lengthOfLastWord(string s)
    {
        // 先将最后面的空格都去除
        while(!s.empty() && s.back() == ' ')
        {
            s.pop_back();
        }
        // 在统计最后一个单词的长度
        int len = 0;
        while(!s.empty() && s.back() != ' ')
        {
            ++len;
            s.pop_back();
        }
        return len;
    }
};
*/

// 编辑距离 
/*
class Solution
{
public:
    // 状态表示dp[i][j]: 表示word1(0,i) 转换成 word2(0,j)最少操作数
    // 状态转移方程
    //      dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[j-1][i-1])
    //      如果word1[i] == word2[j] 则 dp[i][j] = std::min(dp[i][j], dp[i - 1][j - 1])
    // 初始化: dp[i][0] = i , dp[0][j] = j
    // 遍历顺序 & 返回结果
    int minDistance(string word1, string word2)
    {
        int n1 = static_cast<int>(word1.size());
        int n2 = static_cast<int>(word2.size());
        // 建表
        std::vector<std::vector<int>> dp(n1+1,std::vector<int>(n2+1,0));
        // 初始化
        for(int i = 0; i <= n1; ++i) dp[i][0]=i;
        for(int j = 0; j <= n2; ++j) dp[0][j]=j;
        // 填表
        for(int i = 1; i <= n1; ++i)
        {
            for(int j = 1; j <= n2; ++j)
            {
                dp[i][j] = std::min(dp[i - 1][j - 1], std::min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = std::min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp.back().back();
    }
};
*/

// 分割回文串 
/*
class Solution
{
public:
    // 状态表示dp[i][j]: 表示[i,j]区间对应的字符串是否为回文串
    // 状态转移方程:
    //   如果s[i]==s[j]则: 1.i==j dp[i][j]=t 2.i+1==j dp[i][j]=t 3.i+1<j dp[i][j]=dp[i+1][j-1]
    //   如果s[i]!=s[j]则: dp[i][j]=f
    std::vector<std::vector<bool>> dp;
    int n;
    vector<vector<string>> partition(string s)
    {
        n = static_cast<int>(s.size());
        dp = std::vector<std::vector<bool>>(n,std::vector<bool>(n,false));

        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i; j < n; ++j)
            {
                if(s[i] == s[j])
                {
                    if(i+1<j) dp[i][j] = dp[i+1][j-1];
                    else dp[i][j] = true;
                }
                else dp[i][j] = false;
            }
        }
        dfs(s,0);
        return result;
    }

    std::vector<std::vector<std::string>> result;
    std::vector<std::string> path;

    void dfs(const std::string & s, int pos)
    {
        if(pos == n)
        {
            result.push_back(path);
            return;
        }
        for(int i = pos; i < n; ++i)
        {
            if(dp[pos][i])
            {
                path.push_back(s.substr(pos,i-pos+1));
                dfs(s,i+1);
                path.pop_back();
            }
        }
    }
};
*/

// 重排链表
/*
// 顺序表写法:
void reorderList(ListNode* head)
{
    std::vector<ListNode *> v;

    ListNode * curr = head;
    // 先将所有结点地址保存vector中
    while(curr != nullptr)
    {
        v.push_back(curr);
        curr = curr->next;
    }

    int left = 0;
    int right = static_cast<int>(v.size() - 1);
    while(left < right) 
    {
        v[left]->next = v[right];
        left++;
        v[right]->next = v[left];
        right--;
    }

    v[left]->next = nullptr; // 将最后一个结点的next置空
}
*/
// 
/*
// 中间结点+逆置+直接操作
class Solution
{
public:
    ListNode * getMiddleNode(ListNode *head)
    {
        // 利用快慢指针找到中间结点
        ListNode * fast = head;
        ListNode * slow = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next; // 快指针每走两步
            slow = slow->next; // 慢每走一步
        }

        return slow;
    }

    ListNode * reverseList(ListNode * head)
    {
        // 进行链表逆置
        ListNode * curr = head;
        ListNode * prev = nullptr;
        while(curr!=nullptr)
        {
            ListNode * next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    void reorderList(ListNode* head)
    {
        ListNode * mid = getMiddleNode(head);

        ListNode * h1 = head;
        ListNode * h2 = mid->next;
        mid->next = nullptr;

        //h1 = reverseList(h1);
        // 再将后半段的链表进行逆置
        h2 = reverseList(h2);

        while(h1 != nullptr && h2 != nullptr)
        {
            ListNode * nt1 = h1->next;
            ListNode * nt2 = h2->next;
            // h1指向
            h1->next = h2;
            h1 = nt1;
            // h2指向
            h2->next = h1;
            h2=nt2;
        }

        // dfs(h1,h2)
    }

    // 递归
    void dfs(ListNode * h1, ListNode * h2)
    {
        if(h1 == nullptr || h2 == nullptr) return;
        ListNode * nt1 = h1->next;
        ListNode * nt2 = h2->next;

        h1->next = h2;
        h2->next = nt1;
        dfs(nt1,nt2);
    }
};
*/

// 反转字符串中的单词
/*
class Solution
{
public:
    string reverseWords(string s)
    {
        std::string ans;
        // 从后往前将单词放入到ans中
        while(!s.empty())
        {
            if(s.back() == ' ') // 去除多余的空格
            {
                s.pop_back();
            }
            else
            {
                while(!s.empty() && s.back() != ' ')
                {
                    ans.push_back(s.back());
                    s.pop_back();
                }
                ans.push_back(' '); // 让每一个单词之间有一个空格
            }
        }
        ans.pop_back();

        int start = 0;
        int n = static_cast<int>(ans.size());
        while(start < n) // 每一个单词单独逆置
        {
            ssize_t pos = ans.find(' ',start);
            if(pos != std::string::npos)
            {
                std::reverse(ans.begin() + start,ans.begin() + pos);
                start = pos + 1;
            }
            else
            {
                break;
            }
        }
        std::reverse(ans.begin() + start,ans.end());

        return ans;
    }
};
*/

// 颜色分类
// 暴力:
/*
void sortColors(vector<int>& nums) {

        int r = 0;
        int w = 0;
        int b = 0;

        for(auto e : nums)
        {
            if(e == 0) r++;
            else if(e == 1) w++;
            else b++;
        }
        // int n = static_cast<int>(nums.size());
        int pos = 0;
        while(r--) nums[pos++] = 0;
        while(w--) nums[pos++] = 1;
        while(b--) nums[pos++] = 2;
    }
*/
/*
// 单指针
    void sortColors(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        int hd = 0;
        for(int i = 0; i < n; ++i)
        {
            // 将所有0交换到前面
            if(nums[i] == 0) {
                std::swap(nums[i],nums[hd]);
                ++hd;
            }
        }

        for(int i = hd; i < n; ++i)
        {
            // 将所有1交换到前面
            if(nums[i] == 1) {
                std::swap(nums[i],nums[hd]);
                ++hd;
            }
        }
    }
*/

// 二叉树的直径
/*
    // 求二叉树的高度
    int depth(TreeNode* root) {
        if(nullptr == root) return 0;

        int l = depth(root->left);
        int r = depth(root->right);

        return (l>r?l:r) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {

        if(nullptr == root) return 0;

        int ans1 = diameterOfBinaryTree(root->left);
        int ans2 = diameterOfBinaryTree(root->right);

        // 找该结点对应左子树的高度
        int l = depth(root->left);
        // 找该结点对应右子树的高度
        int r = depth(root->right);

        return std::max({ans1,ans2,l+r});
    }
*/
// 简化
/*
class Solution {
    int ans;

    int depth(TreeNode* root) {
        if (root == NULL) return 0;

        int L = depth(root->left);
        int R = depth(root->right);

        ans = max(ans, L + R);

        return max(L, R) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {

        ans = 0;
        depth(root);
        return ans;
    }
};
*/

// 将有序数组转换为二叉搜索树
/*
TreeNode *dfs(vector<int>& nums,int l,int r)
    {
        if(l>r) return nullptr;

        int mid = l + (r - l)/2;

        TreeNode * node = new TreeNode(nums[mid]);
        node->left = dfs(nums,l,mid-1);
        node->right = dfs(nums,mid+1,r);

        return node;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {

        return dfs(nums,0,nums.size()-1);
    }
*/

// 腐烂的橘子
/*
class Solution {
public:

    int dx[4]{0,0,-1,1};
    int dy[4]{-1,1,0,0};

    int orangesRotting(vector<vector<int>>& grid) {

        int nrow = grid.size();
        int ncol = grid.back().size();

        std::queue<pair<int,int>> q;
        int count = 0;
        for(int i = 0; i < nrow; ++i) {
            for(int j = 0; j < ncol; ++j) {
                if(2 == grid[i][j]) {
                    q.push({i,j});
                } else if(grid[i][j] == 1) {
                    ++count;
                }
            }
        }
        int ans = -1;
        while(!q.empty())
        {
            ++ans;
            int n = static_cast<int>(q.size());
            while(n--)
            {
                auto hd = q.front();
                q.pop();

                int i = hd.first;
                int j =hd.second;
                for(int z = 0; z < 4; ++z)
                {
                    int x = i + dx[z];
                    int y = j + dy[z];
                    if(x>=0 && x<nrow && y>=0 && y<ncol && grid[x][y] == 1)
                    {
                        q.push({x,y});
                        grid[x][y] = 2;
                        --count;
                    }
                }
            }
        }
        if(ans == -1) ans = 0;
        return count == 0 ? ans : -1;
    }
};
*/

// 课程表
/*
class Solution {
public:
    // 拓扑排序
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        if(prerequisites.empty()) return true;
        int nrow = prerequisites.size();
        int ncol = prerequisites.back().size();

        std::unordered_map<int,int> in_degree; // 顶点对应的入读
        std::unordered_map<int,std::vector<int>> in_edge; // 与该顶点相连的顶点下标

        // 先获取有多少种课程
        for(int i = 0; i < nrow; ++i)
        {
            // 因为是有向图所有不需要: in_degree[prerequisites[i].back()] = 0;
            in_degree[prerequisites[i].front()] = 0;
            in_edge[prerequisites[i].front()].push_back(prerequisites[i].back());
        }

        // 在记录各个课程的入度
        for(int i = 0; i < nrow; ++i)
        {
            in_degree[prerequisites[i].back()]++;
        }

        std::queue<int> q;

        // 将入度为0的课程加入队列中
        for(auto it = in_degree.begin(); it != in_degree.end(); ++it)
        {
            if(it->second == 0) {
                q.push(it->first);
            }
        }

        while(!q.empty()) {

            auto front = q.front();
            q.pop();

            // 将该对应课程的连接顶点的入度减一
            auto & v = in_edge[front];

            for(auto e : v) {
                // 继续将入度为0的顶点加入队列
                if(--in_degree[e] == 0) {
                    q.push(e);
                }
            }
        }

        // 将入度为0的课程加入队列中
        for(auto it = in_degree.begin(); it != in_degree.end(); ++it)
        {
            if(it->second != 0) {
                return false;
            }
        }
        return true;
    }
};
*/

// 课程表 II
/*
class Solution
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
        int nrow = static_cast<int>(prerequisites.size());

        // 记录每一个顶点的入度
        std::vector<int> in_degree(numCourses,0);
        std::unordered_map<int,std::vector<int>> out_edge;
        for(int i = 0; i < nrow; ++i)
        {
            in_degree[prerequisites[i].front()]++;
            out_edge[prerequisites[i].back()].push_back(prerequisites[i].front());
        }

        // 将入度为零的顶点入队
        std::queue<int> q;
        for(int i = 0; i < static_cast<int>(in_degree.size()); ++i)
        {
            if(in_degree[i] == 0)
            {
                q.push(i);
            }
        }

        std::vector<int> ans;
        while(!q.empty())
        {
            auto hd = q.front();
            q.pop();
            ans.push_back(hd);

            // 将与该顶点相连的顶点的度减一
            auto & v = out_edge[hd];
            for(auto e : v)
            {
                // 如果有顶点的入度被减为零时,则该顶点入队或者入栈
                if(--in_degree[e] == 0)
                {
                    q.push(e);
                }
            }
        }
        // 判断是否还有顶点没有访问到
        for(int i = 0; i < static_cast<int>(in_degree.size()); ++i)
        {
            if(in_degree[i] != 0)
            {
                return {};
            }
        }

        return ans;
    }
};
*/

// 删除有序数组中的重复项 II
/*
class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        int n = static_cast<int>(nums.size());
        if(n <= 2) return n;

        int sw = 2;
        int ft = 2;
        while(ft < n)
        {
            if(nums[sw-2] != nums[ft])
            {
                nums[sw] = nums[ft];
                sw++;
            }
            ft++;
        }

        return sw;
    }
};
*/

// 跳跃游戏
/*
class Solution {
public:
    // 状态表示dp[i]: 表示是否能跳跃到该位置
    // if(dp[j] == true && i-j <= nums[j]) dp[i] = true
    // 初始化: dp[] = false dp[0] = true
    // 遍历顺序: 左到右
    // 返回结果: dp[n-1]
    bool canJump(vector<int>& nums) {

      int n = static_cast<int>(nums.size());

      std::vector<bool> dp(n,false);
      dp[0] = true;

      for(int i = 1; i < n; ++i)
      {
        for(int j = i - 1; j >= 0; --j)
        {
          if(dp[j] && i-j <= nums[j])
          {
            dp[i] = true;
            break;
          }
        }
      }
      return dp.back();
    }
};

class Solution {
public:
    // 贪心
    bool canJump(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        int left = 0;
        int right = 0;

        while(left <= right) {
            if(right >= n - 1) { // 判断是否到达
                return true;
            }
            int maxpos = 0;
            for(int i = left; i <= right; ++i) {
                maxpos = std::max(maxpos,nums[i] + i);
            }
            // 更新区间
            left = right + 1;
            right = maxpos;
        }
        return false; // 不能到达
    }
};
*/

// 替换所有的问号 
/*
class Solution {
public:
    string modifyString(string s) {

        int n = static_cast<int>(s.size());

        for(int i = 0; i < n; ++i)
        {
            // 如果遇到问号则从a~z枚举是否符合相邻字符不同
            if(s[i] == '?')
            {
                for(int ch = 'a'; ch <= 'z'; ++ch)
                {
                    bool flag = false;
                    if(i == 0) { // 最前位置
                        if(ch != s[i+1]) flag = true;
                    } else if(i == n-1) { // 最后位置
                        if(ch != s[i-1]) flag = true;
                    }
                    else {
                        if(ch != s[i-1] && ch != s[i+1]) flag = true;
                    }
                    if(flag) {
                        s[i] = ch;
                        break;
                    }
                    // if((i==0 || s[i-1] != ch) && (i==n-1 || s[i+1] != ch))
                    // {
                    //     s[i] = ch;
                    //     break;
                    // }
                }
            }
        }
        return s;
    }
};
*/

// 提莫攻击
/*
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {

        int n = static_cast<int>(timeSeries.size());

        int ans = 0;
        for(int i = 1; i < n; ++i) {
            // 如果两次发起攻击的间隔大于duration则中毒时间直接加duration
            if(timeSeries[i] - timeSeries[i-1] >= duration) {
                ans += duration;
            } else { // 如果小于则加上两次攻击的时间差
                ans += (timeSeries[i] - timeSeries[i-1]);
            }
        }

        return ans + duration; // 处理最后一次攻击
    }
};
*/

// N 字形变换
/*
class Solution {
public:
    string convert(string s, int numRows) {

        if(numRows <= 1) return s;

        int n = static_cast<int>(s.size());
        // 求公差
        int d = 2 * numRows - 2;
        std::string ans{};

        // 处理第一行
        for(int i = 0; i < n; i += d)
        {
            ans += s[i];
        }

        // 处理中间行
        for(int k = 1; k < numRows - 1 ; ++k)
        {
            for( int i = k, j = d - k; i < n || j < n; i+=d, j+=d )
            {
                if(i < n) ans += s[i];
                if(j < n) ans += s[j];
            }
        }

        // 处理最后一行
        for(int i = numRows - 1; i < n; i += d)
        {
            ans += s[i];
        }

        return ans;
    }
};
*/

//#include <iostream>
//#include <memory>
//using namespace std;
//
//int main() {
//
//    std::weak_ptr<int> wp;
//
//    {
//        std::shared_ptr<int> sp = std::make_shared<int>();
//        wp = sp;
//        std::cout << *sp << " 1 \n";
//    }
//     
//    std::shared_ptr<int> sp = wp.lock();
//
//    std::cout << *sp << " 2 \n"; // 奔溃
//
//    return 0;
//}

// 外观数列
/*
class Solution {
public:
    // 写法一:
    string countAndSay(int n) {

        std::string nums = "1";

        for(int i = 1; i < n; ++i)
        {
            std::string tmp;
            for(int l = 0, r = 0; r < nums.size();)
            {
                while(r < nums.size() && nums[l] == nums[r])
                {
                    r++;
                }
                tmp += std::to_string(r - l) + nums[l];
                l = r;
            }
            nums.swap(tmp);
        }

        return nums;
    }
};
*/
/*
// 写法二:
string countAndSay(int n)
{
    std::string nums = "1";
    for(int i = 1; i < n; ++i)
    {
        int l = 0;
        int r = 0;
        int c = 0;
        int len = static_cast<int>(nums.size());
        std::string tmp;
        while(r < len)
        {
            if(nums[l] == nums[r]) {
                c++;
                r++;
            } else {
                tmp += std::to_string(c) + nums[l];
                l = r;
                c = 0;
            }
        }
        tmp += std::to_string(c) + nums[l];
        nums.swap(tmp);
    }

    return nums;
}
*/

// 数青蛙
/*
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs)
    {
        std::unordered_map<char,int> hash;
        for(auto ch : croakOfFrogs)
        {
            switch(ch)
            {
                case 'c':
                    if(hash['k'] > 0) hash['k']--;
                    hash['c']++;
                    break;
                case 'r':
                    if(hash['c'] > 0)
                    {
                        hash['c']--;
                        hash['r']++;
                    }
                    else return -1;
                    break;
                case 'o':
                    if(hash['r'] > 0)
                    {
                        hash['r']--;
                        hash['o']++;
                    }
                    else return -1;
                    break;
                case 'a':
                    if(hash['o'] > 0)
                    {
                        hash['o']--;
                        hash['a']++;
                    }
                    else return -1;
                    break;
                case 'k':
                    if(hash['a'] > 0)
                    {
                        hash['a']--;
                        hash['k']++;
                    }
                    else return -1;
                    break;
            }
        }
        for(auto e : hash) {
            if(e.first == 'k') continue;
            if(e.second != 0) return -1;
        }
        return hash['k'];
    }
};
*/
/*
int minNumberOfFrogs(string croakOfFrogs)
    {
        std::string t("croak");
        int n = static_cast<int>(t.size());
        std::vector<int> hash(n,0); // ⽤数组来模拟哈希表

        std::unordered_map<char,int> index;
        for(int i = 0; i < n; ++i)
        {
            index[t[i]] = i; // 每一个字符对应的下标
        }

        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                // 如果k大于0则进行--
                if(hash[n-1] > 0) hash[n-1]--;
                hash[0]++;
            }
            else
            {
                // 获取该字符的下标
                int i = index[ch];
                // 如果该字符的前一个为0则直接返回
                if(hash[i - 1] == 0) return -1;
                hash[i - 1]--; // 否则则直接转移
                hash[i]++;
            }
        }
        // 判断是否输出全部五个字母
        for(int i = 0; i < n - 1; i++)
            if(hash[i] != 0)
                return -1;

        return hash[n-1];
    }
*/

// 颜色分类
/*
    // [0,left]: 表示都是0的区间
    // [left+1,i-1]: 表示都是1的区间
    // [i,right-1]: 表示待扫描的区间
    // [right,n-1]: 表示都是2的区间
    void sortColors(vector<int>& nums)
    {
        int left = -1;
        int right = static_cast<int>(nums.size());
        int i = 0;
        while(i < right)
        {
            if(0 == nums[i])
            {
                std::swap(nums[++left], nums[i++]);
            }
            else if(1 == nums[i])
            {
                ++i;
            }
            else if(2 == nums[i])
            {
                std::swap(nums[--right], nums[i]);
            }
        }
    }
*/

// 排序数组
/*
class Solution
{
public:
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(nullptr));
        quickSort(nums,0,nums.size()-1);
        return nums;
    }

    void quickSort(vector<int> &nums, int l, int r)
    {
        if(l>=r) return;

        // 选择一个基准元素
        int key = getRandom(nums,l,r);
        // 进行三块区域划分
        int pos = l;
        int left = l - 1;
        int right = r + 1;
        while(pos < right)
        {
            if(key < nums[pos])
            {
                std::swap(nums[pos], nums[--right]);
            }
            else if(key == nums[pos])
            {
                ++pos;
            }
            else if(key > nums[pos])
            {
                std::swap(nums[pos++], nums[++left]);
            }
        }
        quickSort(nums,l,left);
        quickSort(nums,right,r);
    }

    // 是将获取一个基准数
    int getRandom(vector<int> &nums, int l, int r)
    {
        int t = rand();

        return nums[rand() % (r - l + 1) + l];
    }
};
*/

// 数组中的第K个最大元素
/*
    int findKthLargest(vector<int>& nums, int k)
    {
       return quickSort(nums,0,nums.size()-1,k);
    }

    int quickSort(vector<int> &nums, int l, int r,int k)
    {
        if(l>=r) return nums[l];

        // 按照随机选择的基准元素，将数组分三块
        int key = getRandom(nums,l,r);
        int pos = l;
        int left = l - 1;
        int right = r + 1;
        while(pos < right) {
            if(key < nums[pos]) std::swap(nums[pos], nums[--right]);
            else if(key == nums[pos]) ++pos;
            else if(key > nums[pos]) std::swap(nums[pos++], nums[++left]);
        }

        // 分情况讨论
        int c = r - right + 1;
        int b = right - left - 1;
        if(c>=k) return quickSort(nums,right,r,k);
        else if(c + b >= k) return key;
        else return quickSort(nums, l, left, k - b - c);
    }
*/

/*
#include <vector>
#include <iostream>
#include <queue>
#include <functional>

namespace yx
{
    template<typename T, typename Compare = std::less<T>, typename Container = std::vector<T>>
    class Heap
    {
    public:
        using value_type = T;
        using container_type = Container;
        using size_type = std::size_t;
        using compare_type = Compare;
        using reference = typename container_type::reference;
        using const_reference = typename container_type::const_reference;
        Heap() = default;

        bool empty() const
        {
            return _container.empty();
        }

        size_type size() const
        {
            return _container.size();
        }

        void push(const value_type& val)
        {
            _container.push_back(val);
            upwardAdjustment(static_cast<int>(_container.size()-1));
        }

        // const value_type& top() const
        const_reference top() const
        {
            return _container.front();
        }

        void pop()
        {
            std::swap(_container.front(), _container.back());
            _container.pop_back();
            downwardAdjustment(0, static_cast<int>(_container.size()));
        }

    private:
        container_type _container;
        compare_type _compare;

        void downwardAdjustment(int parent_pos, int n)
        {
            int child_pos = 2 * parent_pos + 1;
            while (child_pos < n)
            {
                // if (child_pos + 1 < n && _container[child_pos] < _container[child_pos + 1]) // 大堆
                if (child_pos + 1 < n && _compare(_container[child_pos], _container[child_pos + 1]))
                {
                    ++child_pos;
                }

                // if (_container[parent_pos] < _container[child_pos])
                if (_compare(_container[parent_pos], _container[child_pos]))
                {
                    std::swap(_container[parent_pos], _container[child_pos]);
                    parent_pos = child_pos;
                    child_pos = 2 * parent_pos + 1;
                }
                else
                {
                    break;
                }
            }
        }

        void upwardAdjustment(int child_pos)
        {
            int parent_pos = (child_pos - 1) / 2;

            while (child_pos > 0)
            {
                // if (_container[parent_pos] < _container[child_pos])
                if (_compare(_container[parent_pos], _container[child_pos]))
                {
                    std::swap(_container[parent_pos], _container[child_pos]);
                    child_pos = parent_pos;
                    parent_pos = (child_pos - 1) / 2;
                }
                else
                {
                    break;
                }
            }

        }
    };

    template<class T>
    void downwardAdjustment(std::vector<T>& _container,int parent_pos, int n)
    {
        int child_pos = 2 * parent_pos + 1;
        while (child_pos < n)
        {
            if (child_pos + 1 < n && _compare(_container[child_pos], _container[child_pos + 1]))
            {
                ++child_pos;
            }

            // if (_container[parent_pos] < _container[child_pos])
            if (_compare(_container[parent_pos], _container[child_pos]))
            {
                std::swap(_container[parent_pos], _container[child_pos]);
                parent_pos = child_pos;
                child_pos = 2 * parent_pos + 1;
            }
            else
            {
                break;
            }
        }
    }

    template<class T,class Compare>
    void heapSort(std::vector<T> &vtr, Compare compare)
    {
        auto down_adjust = [&](int parent_pos, int n)
        {
            int child_pos = 2 * parent_pos + 1;
            while (child_pos < n)
            {
                if (child_pos + 1 < n && compare(vtr[child_pos], vtr[child_pos + 1]))
                {
                    ++child_pos;
                }

                if (compare(vtr[parent_pos], vtr[child_pos]))
                {
                    std::swap(vtr[parent_pos], vtr[child_pos]);
                    parent_pos = child_pos;
                    child_pos = 2 * parent_pos + 1;
                }
                else
                {
                    break;
                }
            }
        };

        int c = static_cast<int>(vtr.size());
        // 建堆
        for (int pos = static_cast<int>((vtr.size() - 1 - 1) / 2); pos >= 0; --pos)
        {
            down_adjust(pos, c);
        }

        // 堆排
        while (c > 0)
        {
            std::swap(vtr.front(), vtr[--c]);
            down_adjust(0, c);
        }
    }
}
*/

//int main() {
//
//    yx::Heap<int> hp;
//
//    hp.push(1);
//    hp.push(2);
//    hp.push(3);
//    hp.push(4);
//
//    while (!hp.empty()) {
//
//        std::cout << hp.top() << "\n";
//        hp.pop();
//    }
//
//    yx::Heap<int, std::greater<int>> hp;
//
//    hp.push(1);
//    hp.push(2);
//    hp.push(3);
//    hp.push(4);
//
//    while (!hp.empty()) {
//
//        std::cout << hp.top() << "\n";
//        hp.pop();
//    }
//
//    std::vector<int> vtr{2,3,3,1,2,5,6,7,8};
//
//    // yx::heapSort(vtr,std::less<int>());
//    yx::heapSort(vtr, std::greater<int>());
//
//
//    for (auto e : vtr)
//    {
//        std::cout << e << "\n";
//    }
//
//    return 0;
//}

// O(1) 时间插入、删除和获取随机元素
/*
class RandomizedSet
{
private:
    std::unordered_map<int,int> hash;
    std::vector<int> vtr;

    // 创建随机数引擎
    std::random_device rd;
    std::default_random_engine eng;
public:

    RandomizedSet() : eng(rd())
    {}

    bool insert(int val)
    {
        // if(hash.find(val) != hash.end())
        if(hash.count(val))
        {
            return false;
        }

        hash.insert( { val, static_cast<int>(vtr.size()) } );
        vtr.push_back(val);

        return true;
    }

    bool remove(int val)
    {
        // if(hash.find(val) == hash.end())
        if(!hash.count(val))
        {
            return false;
        }

        // 获取val删除元素的下标
        int val_pos = hash[val];
        // 获取vtr最后一个元素
        int lastval = vtr.back();
        // 将lastval覆盖掉val的位置
        vtr[val_pos] = lastval;
        // 更新lastval的下标
        hash[lastval] = val_pos;

        vtr.pop_back();
        hash.erase(val);
        return true;
    }

    int getRandom()
    {
        // 定义随机数范围
        int min_pos = 0;
        int max_pos = static_cast<int>(vtr.size() - 1);

        // 创建分布器并生成随机数
        std::uniform_int_distribution<> dist(min_pos, max_pos);
        int randomNum = dist(eng);

        return vtr[randomNum];
    }
};
*/

// 判断子序列
/*
bool isSubsequence(string s, string t) {
    if(s.empty()) {
        return true;
    }
    int nt = static_cast<int>(t.size());
    int ns = static_cast<int>(s.size());

    for(int i = 0, j = 0; j < nt; ++j)
    {
        if(s[i] == t[j]) {
            if(++i == ns) {
                return true;
            }
        }
    }

    return false;
}
*/

// 矩阵置零
/*
class Solution
{
public:
    bool row[201];
    bool col[201];

    void setZeroes(vector<vector<int>>& matrix)
    {
        int nrow = static_cast<int>(matrix.size());
        int ncol = static_cast<int>(matrix.back().size());

        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        std::queue<std::pair<int,int>> q;
        for(int i = 0; i < nrow; ++i)
        {
            for(int j = 0; j < ncol; ++j)
            {
                // 先记录哪些位置为0
                if(matrix[i][j] == 0)
                {
                    q.push({i,j});
                }
            }
        }

        while(!q.empty())
        {
            auto hd = q.front();
            q.pop();

            int i = hd.first;
            int j = hd.second;
            if(!row[i]) // 将对应的行置为0
            {
                matrix[i] = std::vector<int>(ncol,0);
                row[i] = true;
            }
            if(!col[j]) // 将对应的列置为0
            {
                for(int z = 0; z < nrow; ++z)
                {
                    matrix[z][j] = 0;
                }
                col[j] = true;
            }
        }
    }
};
*/

//template<typename T>
//class List
//{
//public:
//    template<typename E>
//    class Node {
//        using node_ptr = Node<E>*;
//    public:
//        E _data;
//        node_ptr _prev;
//        node_ptr _next;
//
//        Node() {
//            _prev = this;
//            _next = this;
//        }
//        Node(const E& data) : _data(data) {
//            _prev = this;
//            _next = this;
//        }
//    };
//
//    using node = Node<T>;
//public:
//    List() : head(new node) {
//        head->_next = head;
//        head->_prev = head;
//    }
//    ~List() {
//        node* curr = head->_next;
//        while (curr != head) {
//            node* next = curr->_next;
//            delete curr;
//            curr = next;
//        }
//        delete head;
//    }
//
//    void addFront(const T& data)
//    {
//        node* newnode = new node(data);
//
//        newnode->_next = head->_next;
//        head->_next->_prev = newnode;
//
//        head->_next = newnode;
//        newnode->_prev = head;
//    }
//
//    void addFront(node* newnode)
//    {
//        newnode->_next = head->_next;
//        head->_next->_prev = newnode;
//
//        head->_next = newnode;
//        newnode->_prev = head;
//    }
//
//    void delFront()
//    {
//        if (head->_next == head || head->_prev == head) {
//            return;
//        }
//
//        node* delnode = head->_next;
//        head->_next = delnode->_next;
//        delnode->_next->_prev = head;
//
//        delete delnode;
//    }
//
//    void addBack(const T& data)
//    {
//        node* newnode = new node(data);
//
//        newnode->_prev = head->_prev;
//        head->_prev->_next = newnode;
//
//        newnode->_next = head;
//        head->_prev = newnode;
//    }
//
//    void addBack(node* newnode)
//    {
//        newnode->_prev = head->_prev;
//        head->_prev->_next = newnode;
//
//        newnode->_next = head;
//        head->_prev = newnode;
//    }
//
//    void delBack()
//    {
//        if (head->_next == head || head->_prev == head) {
//            return;
//        }
//
//        node* delnode = head->_prev;
//        head->_prev = delnode->_prev;
//        delnode->_prev->_next = head;
//
//        delete delnode;
//    }
//
//    void del(node* delnode)
//    {
//        node* prev = delnode->_prev;
//        node* next = delnode->_next;
//
//        prev->_next = next;
//        next->_prev = prev;
//
//        delnode->_next = delnode;
//        delnode->_prev = delnode;
//    }
//
//    node* getFront()
//    {
//        return head->_next;
//    }
//
//    node* getBack()
//    {
//        return head->_prev;
//    }
//private:
//    node* head;
//};
//
//class LRUCache {
//private:
//    using type = List<std::pair<int, int>>::node*;
//    std::unordered_map<int, type> _hash;
//    List<std::pair<int, int>> _list;
//    int _capacity;
//public:
//    LRUCache(int capacity) : _capacity(capacity) {
//
//    }
//
//    int get(int key) {
//        if (_hash.find(key) == _hash.end()) {
//            return -1;
//        }
//
//        type t = _hash[key];
//        _list.del(t);
//        _list.addFront(t);
//
//        return t->_data.second;
//    }
//
//    void put(int key, int value) {
//
//        if (_hash.find(key) == _hash.end()) {
//
//            if (_capacity <= _hash.size()) {
//                type t = _list.getBack();
//                _hash.erase(t->_data.first);
//                _list.delBack();
//            }
//
//            _list.addFront(std::make_pair(key, value));
//            _hash[key] = _list.getFront();
//
//        }
//        else {
//            type t = _hash[key];
//            _list.del(t);
//            _list.addFront(t);
//            t->_data.second = value;
//        }
//    }
//};

// 餐厅过滤器
/*
class Solution {
public:
    // restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance)
    {
        int n = static_cast<int>(restaurants.size());

        std::vector<vector<int>> ans;

        for(int i = n - 1; i >= 0; --i)
        {
            if(veganFriendly == 1 && restaurants[i][2] == 0) {
                continue;
            }

            if(restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance) {

                ans.push_back(restaurants[i]);
            }
        }

        auto compare = [](const std::vector<int> &e1,const std::vector<int> &e2)->bool{
            return e1[1] > e2[1] || (e1[1] == e2[1] && e1[0] > e2[0]);
        };

        std::sort(ans.begin(),ans.end(),compare);

        std::vector<int> result;
        for(auto & e : ans)
        {
            result.push_back(e[0]);
        }

        return result;
    }
};
*/

// 组合总和 II
/*
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> vpath;

    int target;
    int n;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int _target)
    {
        std::sort(candidates.begin(),candidates.end());

        n = static_cast<int>(candidates.size());
        target = _target;

        dfs(candidates,0,0);

        return result;
    }

    void dfs(const vector<int>& candidates,int path,int pos)
    {
        if(path == target)
        {
            result.push_back(vpath);
            return;
        }
        else if(path > target)
        {
            return;
        }

        for(int i = pos; i < n; ++i)
        {
            if(i > pos && candidates[i-1] == candidates[i]) continue;

            vpath.push_back(candidates[i]);
            dfs(candidates,path + candidates[i],i + 1);
            vpath.pop_back();
        }
    }
};
*/

// 旋转图像
/*
// 使用辅助数组
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
        auto matrix_new = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        // 这里也是值拷贝
        matrix = matrix_new;
    }
};
*/

// 赎金信
/*
bool canConstruct(string ransomNote, string magazine)
    {
        std::unordered_map<char,int> hash;
        for(auto ch : magazine)
        {
            hash[ch]++;
        }

        for(char ch : ransomNote)
        {
            if(hash[ch] == 0)
            {
                return false;
            }
            hash[ch]--;
        }

        return true;
    }
*/

// 同构字符串
/*
bool isIsomorphic(string s, string t)
{
    if(s.size() != t.size())
    {
        return false;
    }

    std::unordered_map<char,char> hash;
    int n = static_cast<int>(s.size());

    for(int i = 0; i < n; ++i)
    {
        if(hash.find(s[i]) == hash.end())
        {
            hash.emplace(s[i],t[i]);
        }
        else
        {
            if(hash[s[i]] != t[i])
            {
                return false;
            }
        }
    }

    hash.clear();

    for(int i = 0; i < n; ++i)
    {
        if(hash.find(t[i]) == hash.end())
        {
            hash.emplace(t[i],s[i]);
        }
        else
        {
            if(hash[t[i]] != s[i])
            {
                return false;
            }
        }
    }

    return true;
}
*/

// 柠檬水找零
/*
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (auto& bill: bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) { // 贪心
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};
*/
/*
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        return all_of(bills.cbegin(), bills.cend(), [a = 0, b = 0](int i)mutable { return i == 5 ? ++a : i == 10 ? (++b, a--) : b ? (b-- && a--) : ((a -= 3) > -1); });
    }
};
*/

// 将数组和减半的最少操作次数
/*
class Solution
{
public:
    int halveArray(vector<int>& nums)
    {
        // int sum = std::accumulate(nums.begin(),nums.end(),0);
        std::priority_queue<double> hp;
        double sum = 0;
        // 遍历nums将所有元素压入优先级队列中, 并随便求和
        for(auto e : nums)
        {
            hp.push(e);
            sum += e;
        }

        // 求出和的一半
        double half = sum / 2;

        // 记录操作的次数
        int count = 0;
        while(sum > half)
        {
            // 获取堆顶元素
            double tp = hp.top();
            hp.pop();

            // 堆顶元素减半, 并对sum减去该值
            tp /= 2;
            sum -= tp;

            // 将减半的值重新压入堆中, 并统计操作的次数
            hp.push(tp);
            count++;
        }
        // 返回结果
        return count;
    }
};
*/
/*
  int halveArray(vector<int>& nums) {

        std::priority_queue<double> hp(nums.begin(),nums.end());

        double sum = accumulate(nums.begin(),nums.end(),0.0);
        sum /= 2.0;

        int count = 0;
        while(sum > 0) {
            auto hd = hp.top() / 2.0; hp.pop();
            sum -= hd;
            hp.push(hd);
            count++;
        }
        return count;
    }
*/

// 最大数
/*
class Solution {
public:
    string largestNumber(vector<int> &nums) {
        sort(nums.begin(), nums.end(), [](const int &x, const int &y) {
            long sx = 10, sy = 10;
            while (sx <= x) {
                sx *= 10;
            }
            while (sy <= y) {
                sy *= 10;
            }
            return sy * x + y > sx * y + x;
        });
        if (nums[0] == 0) {
            return "0";
        }
        string ret;
        for (int &x : nums) {
            ret += to_string(x);
        }
        return ret;
    }
};
class Solution {
    public String largestNumber(int[] nums) {
        boolean flag = true;
        for (int num : nums) {
            if (num != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return "0";
        }
        quickSort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (r > l && !compareTo(String.valueOf(nums[r]), String.valueOf(p))) {
                r--;
            }
            swap(nums, l, r);
            while (l < r && compareTo(String.valueOf(nums[l]), String.valueOf(p))) {
                l++;
            }
            swap(nums, l, r);
        }
        quickSort(nums, l + 1, right);
        quickSort(nums, left, r - 1);
    }


    public boolean compareTo(String str1, String str2) {
        int min = Math.min(str1.length(), str2.length());
        boolean flag = false;
        int i = 0;
        for (; i < min; i++) {
            if (str1.charAt(i) > str2.charAt(i)) {
                return true;
            } else if (str1.charAt(i) == str2.charAt(i)) {
                flag = true;
            } else {
                return false;
            }
        }
        if (flag) {
            if (str1.length() > str2.length()) {
                return compareTo(str1.substring(i), str2);
            } else {
                return compareTo(str1, str2.substring(i));
            }
        }
        return false;
    }

    public void swap(int[] nums, int l, int p) {
        int t = nums[l];
        nums[l] = nums[p];
        nums[p] = t;
    }
}
*/

// 单词规律
/*
class Solution {
public:
    bool wordPattern(string pattern, string s)
    {
        // 将s中的每一个单词分别放入数组中
        int ns = static_cast<int>(s.size());
        std::vector<std::string> vstr;
        int pos = 0;
        int bgn = 0;
        // 进行切割
        while(pos < ns)
        {
            if(s[pos] == ' ')
            {
                vstr.push_back(s.substr(bgn,pos-bgn));
                bgn = pos + 1;
            }
            pos++;
        }
        vstr.push_back(s.substr(bgn,pos-bgn));

        // 利用String流获取单词
        // std::vector<std::string> vstr;
        // std::stringstream iss(s);
        // std::string word;
        // while(iss >> word)
        // {
        //     vstr.push_back(word);
        // }

        // 如果长度不一致则直接返回false
        if(pattern.size() != vstr.size()) {
            return false;
        }

        // 进行hash映射
        int np = static_cast<int>(pattern.size());
        std::unordered_map<char,std::string> cshash;
        std::unordered_map<std::string,char> schash;

        for(int i = 0; i < np; ++i)
        {
            if(cshash.find(pattern[i]) != cshash.end() || schash.find(vstr[i]) != schash.end())
            {
                if(cshash[pattern[i]] != vstr[i] || schash[vstr[i]] != pattern[i])
                {
                    return false;
                }
            }
            else
            {
                cshash[pattern[i]] = vstr[i]; schash[vstr[i]] = pattern[i];
            }
        }

        return true;
    }
};
*/
/*
bool wordPattern(string pattern, string s)
    {
        int ns = static_cast<int>(s.size());

        int pos = 0;
        std::unordered_map<char,std::string> ch2str;
        std::unordered_map<std::string,char> str2ch;

        for(char ch : pattern)
        {
            // 如果单词数量与pattern大小不匹配则直接返回false
            if(pos >= ns) {
                return false;
            }

            // 获取一个单词
            int end = pos;
            while(end < ns && s[end] != ' ') {
                end++;
            }

            const std::string &str = s.substr(pos,end - pos);
            pos = end + 1;

            // 判断是否符合双映射性质
            if(ch2str.count(ch) == 1 && ch2str[ch] != str) {
                return false;
            }

            if(str2ch.count(str) == 1 && str2ch[str] != ch) {
                return false;
            }

            ch2str[ch] = str;
            str2ch[str] = ch;
        }

        return pos >= ns;
    }
*/

// 摆动序列
// 贪心
/*
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
};
*/
// 动态规划
/*
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = max(up, down + 1);
            } else if (nums[i] < nums[i - 1]) {
                down = max(up + 1, down);
            }
        }
        return max(up, down);
    }
};
*/

// 存在重复元素 II 
/*
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        int n = static_cast<int>(nums.size());

        // 记录每一个值对应的下标
        std::unordered_map<int,int> hash;
        for(int i = 0; i < n; ++i)
        {
            // 如果该值在i位置之前出现过则
            if(hash.count(nums[i]) == 1)
            {
                // 进行下标比较
                if(std::abs(hash[nums[i]] - i) <= k)
                {
                    return true;
                }
                else
                {
                    // 如果大于k则更新该值对应的下标
                    hash[nums[i]] = i;
                }
            }
            else
            {
                hash[nums[i]] = i;
            }
        }

        //for(int i = 0; i < n; ++i) {
        //    // 如果该值在i位置之前出现过则
        //    if(hash.count(nums[i]) == 1 && std::abs(hash[nums[i]] - i) <= k) {
        //        return true;
        //    }
        //    hash[nums[i]] = i;
        //}

        return false;
    }
};
*/

// 填充每个节点的下一个右侧节点指针 II
/*
class Solution {
public:
    Node* connect(Node* root) {

        if(nullptr == root) {
            return root;
        }

        std::queue<Node *> q;
        q.push(root);

        while(!q.empty()) {

            int n = static_cast<int>(q.size());

            // 记录每一层的前一个结点地址
            Node * next = nullptr;

            for(int i = 0; i < n; ++i) {

                auto hd = q.front();
                q.pop();

                hd->next = next;
                next = hd;
                // 从右到左
                if(hd->right != nullptr) {
                    q.push(hd->right);
                }

                if(hd->left != nullptr) {
                    q.push(hd->left);
                }
            }
        }

        return root;
    }
};
*/

// 二叉树的层平均值 
/*
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (nullptr == root) {
            return {};
        }

        // 创建并初始化队列
        std::queue<TreeNode*> q;
        q.push(root);
        // 记录返回答案
        std::vector<double> ans;

        while (!q.empty()) {

            int n = static_cast<int>(q.size());
            double sum = 0;
            for (int i = 0; i < n; ++i) {

                // 出队
                auto hd = q.front();
                q.pop();

                // 求每一层的和
                sum += hd->val;

                // 入队
                if (hd->left != nullptr) {
                    q.push(hd->left);
                }
                if (hd->right != nullptr) {
                    q.push(hd->right);
                }
            }

            // 记录每一层的平均值
            ans.push_back(sum / n);
        }
        return ans;
    }
};
*/

// 二叉树的锯齿形层序遍历
/*
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (nullptr == root) {
            return {};
        }

        // 创建并初始化队列
        std::queue<TreeNode*> q;
        q.push(root);
        // 记录返回答案
        std::vector<std::vector<int>> result;
        // 通过标记来进行锯齿形层序遍历 
        bool flag = false;
        while (!q.empty()) {

            int n = static_cast<int>(q.size()); // 获取每一层有效结点的个数
            std::vector<int> tmp; // 记录每一层的值

            for (int i = 0; i < n; ++i) {

                // 出队
                auto hd = q.front();
                q.pop();

                tmp.push_back(hd->val);

                // 入队
                if (hd->left != nullptr) {
                    q.push(hd->left);
                }
                if (hd->right != nullptr) {
                    q.push(hd->right);
                }
            }

            if(flag) {
                std::reverse(tmp.begin(),tmp.end());
            }
            flag = !flag;
            result.push_back(tmp);
        }
        return result;
    }
*/

//  二叉搜索树的最小绝对差
/*
class Solution {
public:
    int res{};
    int pre{};

    void dfs(TreeNode * root) {

        if(root == nullptr) {
            return;
        }

        dfs(root->left);

        if(pre == numeric_limits<int>::min()) { // 不存在左操作数
            pre = root->val;
        } else {
            res = std::min(res,root->val - pre);
            pre = root->val;
        }

        dfs(root->right);
    }

    int getMinimumDifference(TreeNode* root) {

        // 初始化
        res = std::numeric_limits<int>::max();
        pre = std::numeric_limits<int>::min();

        dfs(root);
        return res;
    }
};
*/

// 
/*
class Solution {
public:
    // a b
    // ab > ba : a,b
    // ab < ba : b,a
    string largestNumber(vector<int>& nums) {

        // 先将数字转换成字符串
        std::vector<std::string> strs;
        for(auto & e : nums)
        {
            strs.push_back(std::to_string(e));
        }

        // 进行排序
        auto compare = [](const std::string & s1,const std::string &s2){
            return s1 + s2 > s2 + s1;
        };
        std::sort(strs.begin(),strs.end(),compare);

        // 连接
        std::string result;
        for(auto & str : strs)
        {
            result += str;
        }

        if(result[0] == '0') return "0";
        else return result;
    }
};
*/

// 摆动序列
/*
// 统计峰顶及峰谷的数量
int wiggleMaxLength(vector<int>& nums)
{
    int ans = 0;
    int left = 0; // 记录该位置的值与右边的值的差
    int n = static_cast<int>(nums.size());
    for(int i = 0; i < n - 1; ++i)
    {
        int right = nums[i+1] - nums[i];
        if(right == 0) {
            continue;
        }
        // 通过两边的差为异号则说明存在峰顶,峰谷.
        if(left * right <= 0) {
            ans++;
        }
        left = right;
    }

    return ans + 1;
}
*/

// 克隆图
/*
Node* cloneGraph(Node* node) {
    // bfs
    if(node == nullptr) {
        return nullptr;
    }

    std::unordered_map<Node *,Node *> hash;

    std::queue<Node *> q;
    q.push(node);
    hash[node] = new Node(node->val);

    while(!q.empty()) {

        Node * hd = q.front();
        q.pop();

        int n = static_cast<int>(hd->neighbors.size());

        for(int i = 0; i < n; ++i) {

            if(hash.find(hd->neighbors[i]) == hash.end()) {

                hash[hd->neighbors[i]] = new Node(hd->neighbors[i]->val);

                q.push(hd->neighbors[i]);
            }

            hash[hd]->neighbors.push_back(hash[hd->neighbors[i]]);
        }
    }

    return hash[node];
}
*/
/*
class Solution {
public:
    // bfs
    unordered_map<Node*, Node*> visited;
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.find(node) != visited.end()) {
            return visited[node];
        }

        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
        Node* cloneNode = new Node(node->val);
        // 哈希表存储
        visited[node] = cloneNode;

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (auto& neighbor: node->neighbors) {
            cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
};
*/

// 在排序数组中查找元素的第一个和最后一个位置
/*
class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        std::vector<int> ans{-1,-1};
        if(nums.empty()) {
            return ans;
        }

        int n = static_cast<int>(nums.size());

        // 先找左端点的下标
        int left = 0;
        int right = n - 1;
        // [小于target] [小于等于target]
        while(left < right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] >= target) {
                right = mid;
            }
        }

        if(nums[left] != target) {
            return ans;
        }
        ans[0] = left;

        // 再找右端点的下标
        left = 0;
        right = n - 1;
        // [小于等于target] [大于target]
        while(left < right) {
            int mid = left + ((right - left + 1) >> 1);
            if(nums[mid] <= target) {
                left = mid;
            } else if(nums[mid] > target) {
                right = mid - 1;
            }
        }

        ans[1] = left;
        return ans;
    }
};
*/

// 最长递增子序列
/*
// 贪心策略: 如果nums[i] 大于该长度位置的值则nums[i]进行向后面的长度比较, 否则在该长度下更新
    // 二分优化: 如何快速定位nums[i]的更新位置 [小于nums[i]] [大于等于nums[i]]
    int lengthOfLIS(vector<int>& nums)
    {
        int n = static_cast<int>(nums.size());
        std::vector<int> lenval;
        lenval.push_back(nums.front());

        for(int i = 1; i < n; ++i)
        {
            if(nums[i] > lenval.back()) {
                lenval.push_back(nums[i]);
            }
            else {

                int left = 0;
                int right = static_cast<int>(lenval.size() - 1);
                while(left < right)
                {
                    int mid = left + ((right - left) >> 1);
                    if(lenval[mid] < nums[i]) {
                        left = mid + 1;
                    } else if(lenval[mid] >= nums[i]) {
                        right = mid;
                    }
                }

                lenval[left] = nums[i];
            }
        }

        return lenval.size();
    }
*/

// 递增的三元子序列
/*
bool increasingTriplet(vector<int>& nums)
    {
        std::vector<int> lenval;
        lenval.push_back(nums.front());

        int n = static_cast<int>(nums.size());
        for(int i = 1; i < n; ++i)
        {
            int left = 0;
            int right = static_cast<int>(lenval.size() - 1);
            if(nums[i] > lenval.back()) {
                lenval.push_back(nums[i]);
                if(right + 1 >= 3) {
                    return true;
                }
            } else {
                while(left < right)
                {
                    int mid = left + ((right - left) >> 1);
                    if(lenval[mid] < nums[i]) {
                        left = mid + 1;
                    } else if(lenval[mid] >= nums[i]) {
                        right = mid;
                    }
                }

                lenval[left] = nums[i];
            }
        }

        return lenval.size() >= 3;
    }
*/
/*
bool increasingTriplet(vector<int>& nums)
    {
        int a = nums.front();
        int b = std::numeric_limits<int>::max();

        int n = static_cast<int>(nums.size());
        for(int i = 1; i < n; ++i)
        {
           if(nums[i] > a) {
                if(nums[i] > b) {
                    return true; // 如果大于a&&b则长度有3
                } else {
                    b = nums[i]; // 更新长度为2的值
                }
           } else {
                a = nums[i]; // 更新长度为1的值
           }
        }
        return false;
    }
*/

// 最长连续递增序列: 贪心+双指针
/*
int findLengthOfLCIS(vector<int>& nums) {

        int n = static_cast<int>(nums.size());

        int ans = 1;
        for(int i = 0; i < n;) {
            int j = i + 1;
            // 从i开始求出最长连续递增序列
            while(j < n && nums[j-1] < nums[j]) {
                ++j;
            }
            ans = std::max(ans,j - i); // 更新长度
            i = j; // 无需从i+1开始因为在[i+1,j-1]开始的区间没有比i到j的连续递增序列长
        }

        return ans;
    }
*/

// 库存管理 III
/*
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        return smallestK(stock,cnt);
    }
    Solution() {
        srand(time(nullptr));
    }
    // 快速选择算法
    vector<int> smallestK(vector<int>& arr, int k) {
        int n = static_cast<int>(arr.size());
        quickSort(arr, 0, n - 1, k);
        return {arr.begin(),arr.begin() + k};
    }
    void quickSort(vector<int>& arr, int l, int r, int k) {

        if(l >= r) {
            return;
        }
        // 随机获取基准值
        int key = getRandomVal(arr, l, r);
        int bgn = l - 1;
        int end = r + 1;
        int i = l;
        // 将数组分为三块:
        // [l,bgn]: 小于key
        // [bgn + 1, i - 1]: 等于key
        // [i,end - 1]: 带扫描的区间
        // [end, r]: 大于key的区间
        while(i < end) {
            if(arr[i] < key) {
                std::swap(arr[++bgn],arr[i++]);
            } else if(arr[i] == key) {
                i++;
            } else if(arr[i] > key) {
                std::swap(arr[--end],arr[i]); //
            }
        }
        // [l,bgn][bgn+1,end-1][end,r]
        // [a][b][c]
        int a = bgn - l + 1;
        int b = end - 1 - (bgn + 1) + 1;
        int c = r - end + 1;
        if(a > k) {
            quickSort(arr, l, bgn, k);
        } else if(a + b >= k) {
            return;
        } else {
            quickSort(arr, end, r, k - a - b);
        }

    }
    int getRandomVal(vector<int>& arr, int l, int r) {
        int pos = rand() % (r - l + 1) + l;
        return arr[pos];
    }
};
*/

// 买卖股票的最佳时机
/*
   // 暴力解法: 枚举任意两天的售价
    int maxProfit(vector<int>& prices) {
        int n = static_cast<int>(prices.size());
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                if(prices[j] - prices[i] > 0) {
                    ans = std::max(ans,prices[j] - prices[i]);
                }
            }
        }
        return ans;
    }
*/
/*
    // 贪心
    int maxProfit(vector<int>& prices) {

        int n = static_cast<int>(prices.size()); // 数组的长度
        int prev = prices.front(); // i位置之前区间中最小的值
        int ans = 0; // 最大利润

        for(int i = 1; i < n; ++i) {
            if(prices[i] - prev > 0) { // 更新最大利润
                ans = std::max(ans,prices[i] - prev);
            }
            prev = std::min(prev,prices[i]); // 更新最小值
        }

        return ans;
    }
*/

// 买卖股票的最佳时机 II
/*
class Solution {
public:
    // 7
    //            6
    //      5
    //                 4
    //          3
    //
    //   1
    // 找该数组的升序区间
    int maxProfit(vector<int>& prices) {

        int ans = 0;
        int n = static_cast<int>(prices.size());

        for(int i = 0; i < n; ) {

            int j = i + 1;
            // 让j移动到该升区间的end位置
            while(j < n && prices[j] > prices[j - 1]) {
                ++j;
            }
            // 累加收益
            ans += (prices[j - 1] - prices[i]);
            i = j;
        }
        return ans;
    }
};
*/
/*
 // 累加每个递增的点
    int maxProfit(vector<int>& prices) {

        int ans = 0;
        int n = static_cast<int>(prices.size());

        // [ 3 , 6 , 9]
        //   0   1   2
        // prices[2] - prices[0] = (prices[1] - prices[0]) + (prices[2] - prices[1])
        for(int i = 1; i < n; ++i) {
            if(prices[i] > prices[i - 1]) {
                ans += (prices[i] - prices[i - 1]);
            }
        }
        return ans;
    }
*/

// 股票价格跨度
/*
 // 暴力
 std::vector<int> nums;
    int next(int price) {
        nums.push_back(price);
        int ans = 0;
        auto rit = nums.rbegin();

        // 从该数值往回统计有多少小于等于该数值的数
        while(rit != nums.rend()) {
            if(*rit <= price) {
                ++ans;
            } else {
                break;
            }
            ++rit;
        }

        return ans;
    }
*/

// K 次取反后最大化的数组和
/*
class Solution {
public:

    // 统计nums数组中负数的个数negative_count
    // 如果nega >= k 则将nums中的前k个负数都转换为正数
    // 如果nega < k 则先将nums中所有负数都转换为正数
    //      剩余k - nega 次翻转次数, 如果是偶数(对同一个数连续翻转)则直接返回, 如果是奇数则减去最小数值
    int largestSumAfterKNegations(vector<int>& nums, int k) {

        int nega = 0;
        int minval = std::numeric_limits<int>::max();
        int maxsum = 0;
        for(auto e : nums) {

            if(e < 0) {
                ++nega;
            }
            maxsum += std::abs(e);
            minval = std::min(minval,std::abs(e));
        }

        if(k <= nega) { // 负数大于等于翻转次数
            std::sort(nums.begin(),nums.end(),std::less<int>()); // 升序
            for(int i = 0; i < k; ++i) {
                nums[i] = -nums[i];
            }
            int sum = 0;
            for(int e : nums) {
                sum += e;
            }
            maxsum = sum;
        } else {
            if( (k - nega) % 2 != 0 ) {
                maxsum = maxsum - 2*minval;
            }
        }

        return maxsum;
    }
};
*/

// 找出数组的串联值
/*
long long findTheArrayConcVal(vector<int>& nums) {

    int n = static_cast<int>(nums.size());
    int left = 0;
    int right = n - 1;
    long long ans = 0;

    while(left <= right) {

        if(left < right) {
            // 前后位置进行拼接
            std::string str = std::to_string(nums[left]);
            str += std::to_string(nums[right]);
            // 进行累加
            ans += std::atoll(str.c_str());
        } else {
            ans += nums[left];
        }
        ++left;
        --right;
    }
    return ans;
}
*/

// 股票平滑下跌阶段的数目
/*
class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {

        long long ans = 0;
        int n = static_cast<int>(prices.size());
        for(int i = 0; i < n; ) {

            int j = i; // j 表示平滑下降阶段的最后一个位置
            while(j + 1 < n && 1 == (prices[j] - prices[j + 1])) {
                ++j;
            }

            long long c = j - i + 1;
            ans += (( (1 + c ) * c ) / 2);
            i = j + 1;
        }
        return ans;
    }
};

//   4 3 2 1
// 4
// 3
// 2
// 1
// 43
// 32
// 21
// 432
// 321
// 4321
// ( (1 + c ) * c ) / 2
*/

// 股票价格波动 
/*
class StockPrice {
private:
    std::unordered_map<int,int> hash;
    std::map<int,int> minmax;
    int maxtimestamp = 0;
public:
    StockPrice() {

    }

    void update(int timestamp, int price) {

        // 更新最大时间戳
        maxtimestamp = std::max(timestamp,maxtimestamp);
        // 统计每个价格的个数
        ++minmax[price];

        // 判断当前时间戳是否记录过
        if(hash.find(timestamp) != hash.end()) { // 记录过

        int prev_price = hash[timestamp]; // 记录之前价格
        hash[timestamp] = price;
        // ++minmax[price];

        if(--minmax[prev_price] == 0) { // 减去之前价格的个数
            minmax.erase(prev_price);
        }

        } else { // 没有
            hash[timestamp] = price;
            // ++minmax[price];
        }
    }

    int current() {
        return hash[maxtimestamp];
    }

    int maximum() {
        return minmax.rbegin()->first;
    }

    int minimum() {
        return minmax.begin()->first;
    }
};

 //* Your StockPrice object will be instantiated and called as such:
 //* StockPrice* obj = new StockPrice();
 //* obj->update(timestamp,price);
 //* int param_2 = obj->current();
 //* int param_3 = obj->maximum();
 //* int param_4 = obj->minimum();
*/

// 股票的资本损益 
/*
# Write your MySQL query statement below
# case:
# select stock_name,sum(
#     case when operation = 'Sell' then price
#     when operation = 'Buy' then - price
#     end) as capital_gain_loss
#     from Stocks group by stock_name
# if:
# select stock_name,sum(
#     if(operation = 'Buy',-1 * price,price)
#     ) as capital_gain_loss
#     from Stocks group by stock_name;
*/

// 按身高排序 
/*
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

        int n = static_cast<int>(names.size());

        // 将名字与身高绑定在一起
        std::vector<std::pair<std::string,int>> pairs;
        for(int i = 0; i < n; ++i) {
            pairs.emplace_back(names[i],heights[i]);
        }

        // 通过身高进行排序
        auto compare = [](const std::pair<std::string,int> &p1, const std::pair<std::string,int> &p2){
            return p1.second > p2.second;
        };
        std::sort(pairs.begin(),pairs.end(),compare);

        // 记录返回值
        names.clear();
        for(auto & p : pairs) {
            names.push_back(std::move(p.first));
        }
        return names;
    }
*/
/*
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = static_cast<int>(names.size());
        // 因为身高不重复所有可以使用tree_map进行排序
        std::map<int,std::string> treemap;
        for(int i = 0; i < n; ++i) {
            treemap.emplace(heights[i],names[i]);
        }
        // 排序身高,然后根据身高与名字的映射进行返回
        names.clear();
        for(std::map<int,std::string>::reverse_iterator rit = treemap.rbegin(); rit != treemap.rend(); ++rit) {
            names.push_back(std::move(rit->second));
        }
        return names;
    }
*/
/*
    // 由题意可知, names数组和heights数组的下标是⼀⼀对应的,因此我们可以重新创建出来⼀个下标数组,将这个下标数组按照heights[i]的⼤⼩排序
    // 那么,当下标数组排完序之后,⾥⾯的顺序就相当于heights这个数组排完序之后的下标,之后通过排序后的下标依次找到原来的name,完成对名字的排序
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = static_cast<int>(names.size());

        std::vector<int> index;
        for(int i = 0; i < n; ++i) {
            index.push_back(i);
        }

        std::sort(index.begin(),index.end(),[&](const int &i1, const int &i2){
            return heights[i1] > heights[i2]; // 将这个下标数组按照heights[i]的⼤⼩排序
        });

        std::vector<std::string> result;
        for(auto e : index) {
            result.push_back(names[e]); // 之后通过排序后的下标依次找到原来的name,完成对名字的排序
        }
        return result;
    }
*/

// 优势洗牌
/*
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = static_cast<int>(nums1.size());
        // 创建下标数组
        std::vector<int> index1;
        std::vector<int> index2;
        for(int i = 0; i < n; ++i) {
            index1.push_back(i);
            index2.push_back(i);
        }
        // 排序下标数组
        std::sort(index1.begin(),index1.end(),[&](const int &i1, const int &i2){
            return nums1[i1] < nums1[i2];
        });
        std::sort(index2.begin(),index2.end(),[&](const int &i1, const int &i2){
            return nums2[i1] < nums2[i2];
        });
        // 贪心策略:
        // 如果nums1[i] 小于等于 nums2[left] 则让nums[i] 与 nums[right] 比较
        // 如果nums[i] 大于 nums2[left] 则直接比较
        std::vector<int> result(n);
        for(int i = 0, left = 0, right = n - 1; i < n; ++i) {
            if(nums1[index1[i]] <= nums2[index2[left]]) {
                result[index2[right--]] = nums1[index1[i]];
            } else {
                result[index2[left++]] = nums1[index1[i]];
            }
        }
        return result;
    }
};
*/

/*
// 1) 字符串拆分成数组，如”ab&&2”通过”&&”做分隔符，分割得到字符串数组[“ab”,”2”]
std::vector<std::string> spiltString(std::string &str)
{
    std::vector<std::string> result;
    std::string sep = "&&"; // 分隔符
    int start = 0; // 表示子串查找的起始位置

    int n = static_cast<int>(str.size()); // 原字符串的长度

    while(start < n)
    {
        int pos = str.find(sep ,start); // 查找分隔符

        if(pos != std::string::npos)
        {
            result.push_back(str.substr(start, pos - start)); // 获取子串

            start = pos + static_cast<int>(sep.size()); // 更新查找的起始位置
        }
        else

        {
            break;
        }

    }
    return result; //  返回结果
}

// 实现字符串组合，如[“ab”,”2”]通过”&&”分隔符，组合成字符串”ab&&2”
std::string jointString(std::vector<std::string> &vstr)
{
    int n = static_cast<int>(vstr.size());
    std::string ans = vstr.front();
    std::string sep = "&&";

    for(int i = 1; i < n; ++i)
    {
        ans += vstr[i];
        ans += sep;
    }
    return ans;
}
*/

/*
// 1000个数范围是[0,999]，有且只有2个相同的数，请编写程序找出来
int findNumber(std::vector<int> &nums)
{
    int n = static_cast<int>(nums.size()); // 数组大小
    std::unordered_map<int,int> hash; // 统计每个数出现的次数
    for(int i = 0; i < n; ++i)
    {

        if(++hash[nums[i]] == 2)
        {
            return nums[i];
        }
    }

    return -1; // 没有找到
}
*/

// 最长回文串 
/*
  int longestPalindrome(string s)
    {
        std::unordered_map<int,int> hash;
        // 统计每一个字符的个数
        for(auto ch : s)
        {
            hash[ch]++;
        }

        int len = 0;
        bool flag = false;
        for(auto iter : hash)
        {
            if(!flag && iter.second % 2 == 1)
            {
                flag = true;
            }
            len += (iter.second / 2 * 2); // 让奇数变偶数
        }
        return flag ? len + 1 : len;
    }
*/

// 增减字符串匹配
/*
class Solution {
public:
    vector<int> diStringMatch(string s)
    {
        int left = 0;
        int right = static_cast<int>(s.size());
        std::vector<int> ans;
        for(auto ch : s)
        {
            if(ch == 'I')
            {
                ans.push_back(left++);
            }
            else
            {
                ans.push_back(right--);
            }
        }
        ans.push_back(left);
        return ans;
    }
};
*/

// 分发饼干
/*
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s)
    {
        // 先对g及s排序
        std::sort(g.begin(), g.end(), std::less<int>());
        std::sort(s.begin(), s.end(), std::less<int>());
        // i:表示当前最小胃口的位置
        // j:表示当前最小尺寸的位置
        // 贪心策略: 如果当前尺寸不能满足则销毁当前的往后面寻找更大的尺寸
        //              如果当前尺寸能满足则i++,j++,ans++
        int ans = 0;
        int m = static_cast<int>(g.size());
        int n = static_cast<int>(s.size());
        for(int i = 0, j = 0; j < n && i < m; )
        {
            if(g[i] <= s[j]) {
                j++;
                i++;
                ans++;
            } else {
                j++;
            }
        }
        return ans;
    }
};
*/

// 最优除法
/*
// 因为nums[i] > 2
    // 所有 a / (b / c / d / e / f) = a * c * d * e * f / b
    string optimalDivision(vector<int>& nums) {
        int n = static_cast<int>(nums.size());

        if(1 == n) {
            return std::to_string(nums.front());
        }
        if(n == 2) {
            return std::to_string(nums.front()) + "/" + std::to_string(nums.back());
        }

        std::string expression = std::to_string(nums[0]) + "/(" + std::to_string(nums[1]);
        for(int i = 2; i < n; ++i)
        {
            expression += ("/" + std::to_string(nums[i]));
        }
        expression.push_back(')');
        return expression;
    }
*/

// 跳跃游戏 II
/*
// class Solution {
// public:
//     // 状态表示dp[i]: 表示从0到i位置的最少跳跃数
//     // 状态转移方程: dp[i] = 如果j+nums[j] >= i 则min(dp[j]) (0 <j<= i-1)
//     // 初始化: dp[i] = MAX_INT dp[0] = 0
//     // 遍历顺序: 从左到右
//     // 返回结果: dp[n - 1]
//     int jump(vector<int>& nums) {
//         // 建表 + 初始化
//         int n = static_cast<int>(nums.size());
//         std::vector<int> dp(n,std::numeric_limits<int>::max());
//         dp[0] = 0;
//         // 填表
//         for(int i = 0; i < n; ++i)
//         {
//             for(int j = i - 1; j >= 0; --j)
//             {
//                 if(j + nums[j] >= i)
//                 {
//                     dp[i] = std::min(dp[i],dp[j] + 1);
//                 }
//             }
//         }
//         // 返回结果
//         return dp[n - 1];
//     }
// };

class Solution {
public:
    // 贪心策略: 1.left及right表示第k次跳跃则能到达的区间, 如果right位置大于n - 1则表示能到达nums[n-1]处
    //          2. 每次扫描[left,right]区间, 记录nums[i] + i的最大值
    //          3. 遍历区间完毕后更新left及right & 判断是否到达nums[i]返回最少跳跃数
    // 跳跃区间类似层序遍历
    // [ 2 , 3 , 1 , 1 , 4 ]
    //   -   -----   -----
    int jump(vector<int>& nums) {
        int n = static_cast<int>(nums.size());

        //if(n <= 1) {
        //    return 0;
        //}

        int left = 0;
        int right = 0;
        int ans = 0;

        while(left <=  right) {

            // 判断是否到达
            if(right >= n - 1) {
                return ans;
            }
            int maxpos = 0;
            for(int i = left; i <= right; ++i) {
                maxpos = std::max(maxpos,nums[i] + i);
            }
            // 更新区间
            left = right + 1;
            right = maxpos;
            ++ans;
        }

        // while(right < n) {
        //    int maxpos = 0;
        //    for(int i = left; i <= right; ++i) {
        //        maxpos = std::max(maxpos,nums[i] + i);
        //    }
        //    left = right + 1;
        //    right = maxpos;
        //    ans++;
        //    if(right >= n - 1) {
        //        break;
        //    }
        //}

        return ans;
    }
};
*/

// 加油站 
/*
class Solution {
public:
    // 暴力解法: 枚举以所有位置点，判断是否能行驶一圈
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = static_cast<int>(gas.size());

        for(int start = 0; start < n; ++start)
        {
            int rest = gas[start] - cost[start];
            if(rest >= 0) // 判断是否能从该位置点开始
            {
                int pos = (start + 1) % n;
                for(; pos != start; pos = (pos + 1) % n)
                {
                    rest = rest + gas[pos] - cost[pos];
                    if(rest < 0) { // 判断油量是否能到达下一个位置点
                        break;
                    }
                }
                if(pos == start) { // 判断是否走完一圈
                    return start;
                }
            }
        }
        return -1;
    }
};
*/
/*
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    // 贪心策略：
    // a + b + c + d + e + f < 0 (gas[i] - cost[i])
    // b + c + d + e + f < 0 依然小于0
    // 所有无需从[b,c,d,e,f]开始直接从f位置之后开始
    int n = static_cast<int>(gas.size());
    for(int start = 0; start < n; ++start) // 依次枚举所有的起点
    {
        int rest = 0;
        int step = 0;
        for(; step < n; ++step) // // 枚举向后⾛的步数
        {
            int index = (start + step) % n; // // 求出⾛step步之后的下标
            rest = rest + gas[index] - cost[index];
            if(rest < 0) {
                break;
            }
        }
        if(step == n) {
            return start;
        }
        start = start + step; // 优化
    }

    return -1;
}
*/

// 单调递增的数字
/*
// 暴力解法一:
    int monotoneIncreasingDigits(int n) {
        auto isIncrease = [](const std::string &str){
            int n = static_cast<int>(str.size());
            for(int i = 1; i < n; ++i)
            {
                if(str[i - 1] > str[i]) {
                    return false;
                }
            }
            return true;
        };

        int num = n;
        while(num >= 0)
        {
            std::string str = std::to_string(num);
            if(isIncrease(str)) {
                return num;
            }
            --num;
        }
        return -1;
    }
// 暴力解法二:
    int monotoneIncreasingDigits(int n) {
        auto isIncrease = [](int num){
            int prev = num % 10;
            num /= 10;
            while(num > 0) {
                int curr = num % 10;
                num /= 10;
                if(prev < curr) {
                    return false;
                }
                prev = curr;
            }

            return true;
        };

        int num = n;
        while(num >= 0)
        {
            if(isIncrease(num)) {
                return num;
            }
            --num;
        }
        return -1;
    }
*/
/*
// 贪心：
int monotoneIncreasingDigits(int n)
{
    string s = to_string(n); // 把数字转化成字符串

    int i = 0, m = s.size();
    // 找第⼀个递减的位置
    while (i + 1 < m && s[i] <= s[i + 1]) i++;

    if (i + 1 == m) return n; // 判断⼀下特殊情况

    // 回推
    while (i - 1 >= 0 && s[i] == s[i - 1]) i--;
    s[i]--;

    for (int j = i + 1; j < m; j++) s[j] = '9';

    return stoi(s);
}
*/

// 查找和最小的 K 对数字
// error:
/*
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        std::priority_queue<int,std::vector<int>,std::greater<int>> hp1;
        std::priority_queue<int,std::vector<int>,std::greater<int>> hp2;
        for(auto e : nums1) {
            hp1.push(e);
        }
        for(auto e : nums2) {
            hp2.push(e);
        }
        std::vector<std::vector<int>> pairs;
        while(!hp1.empty() && !hp2.empty() && k > 0) {
            pairs.push_back({hp1.top(),hp2.top()});
            --k;
            
            if(hp1.size() == 1) {
                hp2.pop();
                continue;
            } 

            if(hp2.size() == 1) {
                hp1.pop();
                continue;
            }

            if(hp1.top() > hp2.top()) {
                hp1.pop();
            } else if(hp1.top() < hp2.top()){
                hp2.pop();
            } else {
                int top = hp1.top();
                hp1.pop();
                hp2.pop();
                if(hp1.top() == top) {
                    hp2.push(top);
                } else {
                    hp1.push(top);
                }
            }
        }
        return pairs;
    }
};
*/
// 暴力解法一:
/*
vector<vector<int>> kSmallestPairs(const vector<int>& nums1, const vector<int>& nums2, int k) {

    int n1 = static_cast<int>(nums1.size());
    int n2 = static_cast<int>(nums2.size());
    std::vector<std::vector<int>> pairs;
    // 生成nums1与nums2组成的所有对值
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < n2; ++j) {
            std::vector<int> v;
            v.push_back(nums1[i]);
            v.push_back(nums2[j]);
            pairs.push_back(std::move(v));
            //pairs.push_back({ nums1[i],nums2[j] });
        }
    }

    // 对pairs排升序
    std::sort(pairs.begin(), pairs.end(), [](const std::vector<int>& v1, const std::vector<int>& v2) {
        //return (v1.front() + v1.back()) < (v2.front() + v2.back());
        return (v1[0] + v1[1]) < (v2[0] + v2[1]);
        });

    std::vector<std::vector<int>> result;

    int n = static_cast<int>(pairs.size());

    for (int i = 0; i < n && i < k; ++i) {
        result.push_back(pairs[i]);
    }

    return result;
}
*/
// 暴力解法二:
/*
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

    int n1 = static_cast<int>(nums1.size());
    int n2 = static_cast<int>(nums2.size());

    // 建大堆，小的对值往下沉
    auto compare = [](const std::vector<int>& v1, const std::vector<int>& v2){
        return (v1.front() + v1.back()) < (v2.front() + v2.back());
    };
    std::priority_queue<std::vector<int>,std::vector<std::vector<int>>,decltype(compare)> maxhp(compare);

    std::vector<std::vector<int>> pairs;
    // 生成nums1与nums2组成的所有对值
    for(int i = 0; i < n1; ++i) {
        for(int j = 0; j < n2; ++j) {

            std::vector<int> v;
            v.push_back(nums1[i]);
            v.push_back(nums2[j]);

            int n = static_cast<int>(maxhp.size());
            if(n < k) { // 先存入k个对值
                maxhp.push(std::move(v));
            } else {
                if(compare(v,maxhp.top())) {
                    maxhp.pop(); // 将大的对值弹出
                    maxhp.push(std::move(v));
                }
            }
        }
    }

    // 返回答案
    std::vector<std::vector<int>> result;
    while(!maxhp.empty()) {
        result.push_back(maxhp.top());
        maxhp.pop();
    }
    return result;
}
*/
/*
// 
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };

        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> ans;
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < min(k, m); i++) {
            pq.emplace(i, 0);
        }
        while (k-- > 0 && !pq.empty()) {
            auto [x, y] = pq.top();
            pq.pop();
            ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
            if (y + 1 < n) {
                pq.emplace(x, y + 1);
            }
        }

        return ans;
    }
};
*/
// 二分:
/*
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size();
    int n = nums2.size();
    auto count = [&](int target) {
        long long cnt = 0;
        int start = 0;
        int end = n - 1;
        while (start < m && end >= 0) {
            if (nums1[start] + nums2[end] > target) {
                end--;
            }
            else {
                cnt += end + 1;
                start++;
            }
        }
        return cnt;
    };

    // 二分查找第 k 小的数对和的大小
    int left = nums1[0] + nums2[0];
    int right = nums1.back() + nums2.back();
    int pairSum = right;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (count(mid) < k) {
            left = mid + 1;
        }
        else {
            pairSum = mid;
            right = mid - 1;
        }
    }

    vector<vector<int>> ans;
    int pos = n - 1;
    // 找到小于目标值 pairSum 的数对
    for (int i = 0; i < m; i++) {
        while (pos >= 0 && nums1[i] + nums2[pos] >= pairSum) {
            pos--;
        }
        for (int j = 0; j <= pos && k > 0; j++, k--) {
            ans.push_back({ nums1[i], nums2[j] });
        }
    }
    // 找到等于目标值 pairSum 的数对
    pos = n - 1;
    for (int i = 0; i < m && k > 0; i++) {
        int start1 = i;
        while (i < m - 1 && nums1[i] == nums1[i + 1]) {
            i++;
        }
        while (pos >= 0 && nums1[i] + nums2[pos] > pairSum) {
            pos--;
        }
        int start2 = pos;
        while (pos > 0 && nums2[pos] == nums2[pos - 1]) {
            pos--;
        }
        if (nums1[i] + nums2[pos] != pairSum) {
            continue;
        }
        int count = (int)min((long)k, (long)(i - start1 + 1) * (start2 - pos + 1));
        for (int j = 0; j < count && k > 0; j++, k--) {
            ans.push_back({ nums1[i], nums2[pos] });
        }
    }
    return ans;
}

long min(long num1, long num2) {
    return num1 <= num2 ? num1 : num2;
}
*/

// 归并
/*
class Solution
{
public:
    std::vector<int> temp;
    vector<int> sortArray(vector<int>& nums)
    {
        int n = static_cast<int>(nums.size());
        temp.resize(n);
        mergeSort(nums, 0, n - 1);
        return nums;
    }

    void mergeSort(std::vector<int> &nums, int left, int right)
    {
        if(left >= right)
        {
            return;
        }
        // 1. 选择中间点划分区间
        int mid = left + ((right - left) >> 1);
        // 后序 2. 把左右区间排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int pos = 0;
        int cur1 = left;
        int cur2 = mid + 1;
        // 3. 合并两个有序数组
        while(cur1 <= mid && cur2 <= right)
        {
            temp[pos++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        // 4. 处理没有遍历完的数组
        while(cur1 <= mid)
        {
            temp[pos++] = nums[cur1++];
        }
        while(cur2 <= right)
        {
            temp[pos++] = nums[cur2++];
        }
        // 5. 还原
        for(int i = left; i <= right; ++i)
        {
            nums[i] = temp[i - left];
        }
    }
};
*/

// 交易逆序对的总数
/*
class Solution {
public:
    std::vector<int> temp;
    int reversePairs(vector<int>& record) {
        int n = static_cast<int>(record.size());
        temp.resize(n);
        return merge(record, 0, n - 1);
    }

    // 总逆序对数 = 左区间 + 右区间 + (左 > 右)
    int merge(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        // 求出中间下标划分左右区间
        int res = 0;
        // int mid = left + ((right - left) >> 1);
        int mid = (left + right) >> 1;
        res += merge(nums, left, mid);
        res += merge(nums, mid + 1, right);

        int curr1 = left;
        int curr2 = mid + 1;
        int pos = 0;

        // // 策略一：进行升序排序，快速统计出某个数前⾯有多少个数⽐它大
        // while(curr1 <= mid && curr2 <= right)
        // {
        //     if(nums[curr1] <= nums[curr2]) {
        //         temp[pos++] = nums[curr1++];
        //     } else {
        //         res += (mid - curr1 + 1);
        //         temp[pos++] = nums[curr2++];
        //     }
        // }
        // 策略二：进行降排序，快速统计出某个数后⾯有多少个数⽐它小
        while(curr1 <= mid && curr2 <= right)
        {
            if(nums[curr1] <= nums[curr2]) {
                temp[pos++] = nums[curr2++];
            } else {
                res += (right - curr2 + 1);
                temp[pos++] = nums[curr1++];
            }
        }
        // 处理没有遍历完的数组
        while(curr1 <= mid)
        {
            temp[pos++] = nums[curr1++];
        }
        while(curr2 <= right)
        {
            temp[pos++] = nums[curr2++];
        }
        // 还原
        for(int i = left; i <= right; ++i)
        {
            nums[i] = temp[i - left];
        }
        return res;
    }
};
*/

// 计算右侧小于当前元素的个数 翻转对
/* 
class Solution {
public:
    std::vector<int> counts;
    vector<int> countSmaller(vector<int>& nums) {

        int n = static_cast<int>(nums.size());
        counts.resize(n,0);

        // 值与下标绑定
        std::vector<std::pair<int,int>> pairs;
        for(int i = 0; i < n; ++i)
        {
            pairs.push_back({nums[i],i});
        }

        merge(pairs, 0, n - 1);

        return counts;
    }

    // 在当前元素的后面，有多少个元素比该元素小
    void merge(std::vector<std::pair<int,int>> &pairs, int left, int right) {
        if(left >= right) {
            return;
        }

        // 划分两个区间
        int mid = ((right - left) >> 1) + left;
        // 先处理左右两部分
        merge(pairs, left, mid);
        merge(pairs, mid + 1, right);

        std::vector<std::pair<int,int>> temp(right - left + 1);

        // 处理⼀左⼀右的情况
        int cur1 = left;
        int cur2 = mid + 1;
        int pos = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(pairs[cur1].first > pairs[cur2].first) {
                counts[pairs[cur1].second] += (right - cur2 + 1);
                temp[pos++] = pairs[cur1++];
            } else {
                temp[pos++] = pairs[cur2++];
            }
        }
           
        // 处理剩下的排序过程
        while(cur1 <= mid) {
            temp[pos++] = pairs[cur1++];
        }
        while(cur2 <= right) {
            temp[pos++] = pairs[cur2++];
        }
        // 复原
        for(int i = left; i <= right; ++i) {
            pairs[i] = temp[i - left];
        }
    }
};
*/

// 翻转对
/*
class Solution {
public:
    int tmp[50010];
    int reversePairs(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        return merge(nums, 0, n - 1);
    }

    int merge(std::vector<int> &nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        // 1. 先根据中间元素划分区间
        int mid = (left + right) >> 1;
        // [left, mid] [mid + 1, right]

        // 2. 先计算左右两侧的翻转对
        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);

        // 3. 先计算翻转对的数量
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid) {
            while(cur2 <= right && nums[cur1] <= nums[cur2] * 2) cur2++;
            if(cur2 > right) break;

            ret += (right - cur2 + 1);
            cur1++;
        }

        // 4. 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++)
        nums[j] = tmp[j];
        return ret;
    }
};
*/

// 坏了的计算器
/*
class Solution {
public:
    // 正难则反：另 target 变为 startValue
    // 当 target < startValue 时 target加一
    // 当 target > startValue 时
    //      target为奇数则加一
    //      target为偶数则除二
    // 当 target == startValue 时 返回最小操作次数
    int brokenCalc(int startValue, int target) {

        int end = target;
        int start = startValue;
        int opt = 0;

        while(end != start) {

            if(end < start) {
                end++;
            } else {
                if(end % 2 == 1) {
                    end++;
                } else {
                    end /= 2;
                }
            }
            opt++;
        }
        return opt;
    }
};
*/

// 合并区间
/*
class Solution
{
public:
    // 对区间进行排序：左端点 or 右端点
    // [a b]
    //  1. [c d] (b=>c>=a d<=b) 在区间里面
    //  2. [e f] (b>=e>=a f>b) 与区间相交
    //  3. [g h] (g==b h>b) 与区间右端点重合
    //  4. [i j] (i>b) 在区间右边
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {

        // 以区间左端点进行排序
        std::sort(intervals.begin(),intervals.end(),[](const std::vector<int> &v1, const std::vector<int> &v2){
            return v1.front() < v2.front();
        });

        // 维护当前区间
        int left = intervals.front().front();
        int right = intervals.front().back();
        // 记录返回结果
        std::vector<std::vector<int>> result;
        // 合并区间
        int n = static_cast<int>(intervals.size());
        for(int i = 1; i < n; ++i)
        {
            if(right >= intervals[i].front())
            {
                // 如果可以合并则更新最右端点
                right = std::max(right,intervals[i].back());
            }
            else
            {
                result.push_back({left,right}); // 记录可合并的最长区间
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        result.push_back({left,right});
        return result;
    }
};
*/
// 插入区间
/*
  vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        // 进行一起排序
        intervals.push_back(newInterval);
        // 以区间左端点进行排序
        std::sort(intervals.begin(),intervals.end(),[](const std::vector<int> &v1, const std::vector<int> &v2){
            return v1.front() < v2.front();
        });

        // 维护当前区间
        int left = intervals[0][0];
        int right = intervals[0][1];
        // 记录返回结果
        std::vector<std::vector<int>> result;
        // 合并区间
        int n = static_cast<int>(intervals.size());
        for(int i = 1; i < n; ++i) {
            if(right >= intervals[i][0]) {
                // 如果可以合并则更新最右端点
                right = std::max(right,intervals[i][1]);
            } else {
                result.push_back({left,right}); // 记录可合并的最长区间
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        result.push_back({left,right});
        return result;
    }
*/

// 无重叠区间
/*
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 以区间左端点进行排序
        std::sort(intervals.begin(),intervals.end(),[](const std::vector<int> &v1, const std::vector<int> &v2){
            return v1.front() < v2.front();
        });

        // 维护当前区间
        int left = intervals.front().front();
        int right = intervals.front().back();
        // 记录结果
        int result = 0;
        // 合并区间
        int n = static_cast<int>(intervals.size());
        for(int i = 1; i < n; ++i)
        {
            if(right > intervals[i].front())
            {
                right = std::min(right,intervals[i].back());
                result++; // 将大区间删去
            }
            else
            {
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        return result;
    }
*/

// 用最少数量的箭引爆气球
/*
class Solution {
public:

    // 当对区间排序后:
    // 1. 能够合并的区间是连续的（求并集）
    // 2. 互相重叠的区间是连续的（求交集）
    int findMinArrowShots(vector<vector<int>>& points)
    {
        int n = static_cast<int>(points.size());

        // 对左端点进行升序排序
        std::sort(points.begin(),points.end(),[](const std::vector<int> &v1,const std::vector<int> &v2){
            return v1[0] < v2[0];
        });

        int left = points[0][0];
        int right = points[0][1];
        int ans = 1;
        for(int i = 1; i < n; ++i)
        {
            int a = points[i][0];
            int b = points[i][1];
            // 如果right >= a
            //  区间重叠，并且更新left = max(left,a) right = min(right,b)
            // 否则
            //  l = a , r = b
            if(right >= a) {
                left = std::max(left,a);
                right = std::min(right,b);
            } else {
                ++ans;

                left = a;
                right = b;
            }
        }

        return ans;
    }
};
*/

// 最小操作次数使数组元素相等
/*
class Solution {
public:
    int minMoves(vector<int>& nums) {
        // 求对立事件，操作一次: 让一个数减一
        int minnum = *std::min_element(nums.begin(),nums.end());
        int ans = 0;
        for(auto e : nums)
        {
            ans += (e - minnum);
        }

        return ans;
    }
};
*/

// 整数替换
/*
class Solution
{
public:
    std::unordered_map<long long,long long> memo;

    int integerReplacement(int n)
    {
        return dfs(n);
    }

    long long dfs(long long n)
    {
        if(1 == n) // 如果替换到1则直接返回0
        {
            return 0;
        }

        if(memo.find(n) != memo.end()) // 判断该数是否已经求出最小操作数
        {
            return memo[n];
        }

        long long ret = 0;
        // 根据奇偶进行操作
        if(n % 2 == 0)
        {
            ret = dfs(n / 2);
            // memo[n] = ret + 1;
            // return ret + 1;
        }
        else
        {
            ret = dfs(n - 1);
            ret = std::min(ret, dfs(n + 1));
            // memo[n] = ret + 1;
            // return ret + 1;
        }
        memo[n] = ret + 1; // 记录
        return ret + 1;
    }
};
*/
// 贪心：
/*
    int integerReplacement(int n)
    {
        int ret = 0;
        while(n > 1)
        {
            // 如果是偶数则直接处理
            if(n % 2 == 0)
            {
                n /= 2;
                ret+=1;
            }
            else
            {
                if(n == 3)
                {
                    ret += 2;
                    n = 1;
                }
                else if(n % 4 == 1)
                {
                    ret += 2;
                    n /= 2;
                }
                else
                {
                    ret += 2;
                    n = n / 2 + 1;
                }
            }
        }
        return ret;
    }
*/

// 俄罗斯套娃信封问题
// 动态规划：
/*
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {

        // 先按照宽度进行排序，排完序后就能以高度来判断两份信件是否可以“套娃”
        std::sort(envelopes.begin(), envelopes.end(), [](std::vector<int> &v1, std::vector<int> &v2) {
            return v1[0] < v2[0];
        });
        int n = static_cast<int>(envelopes.size());
        // 状态表示: dp[i]表示以i位置为结尾的最长递增子序列的长度
        std::vector<int> dp(n,1);
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i - 1; j >= 0; --j) {
                // 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里
                // 状态转移方程: 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ---> dp[i] = max(dp[j] + 1)
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = std::max(dp[i],dp[j] + 1);
                }
            }
            ans = std::max(ans,dp[i]);
        }

        return ans;
    }
};
*/
// 贪心+二分
/*
int maxEnvelopes(vector<vector<int>>& envelopes) {

        std::sort(envelopes.begin(), envelopes.end(), [](std::vector<int> &v1, std::vector<int> &v2){
            if(v1[0] == v2[0]) { // 如果宽度相等则按照高度降序排
                return v1[1] > v2[1];
            } else { // 否则按照宽度升序排
                return v1[0] < v2[0];
            }
        });

        // 初始化
        std::vector<int> ans;
        ans.push_back(envelopes[0][1]);

        int n = static_cast<int>(envelopes.size());
        for(int i = 1; i < n; ++i) {

            if(ans.back() < envelopes[i][1]) {

                ans.push_back(envelopes[i][1]);

            } else {
                int left = 0;
                int right = static_cast<int>(ans.size() - 1);
                // 找左端点
                while(left < right) {
                    int mid = ((right - left) >> 1) + left;
                    if(ans[mid] >= envelopes[i][1]) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                ans[left] = envelopes[i][1];
            }
        }
        return ans.size();
    }
*/

// 可被三整除的最大和
/*
class Solution {
public:
    // 状态表示dp[i][j]: 从前i个数中选取若干，MOD 3 后为j的最大数
    int maxSumDivThree(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        // 建表+初始
        std::vector<std::vector<int>> dp(n + 1,std::vector<int>(3,-0x3f3f3f3f));
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i) {
            // 转移方程：
            if (nums[i - 1] % 3 == 0) {
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]);
            } else if (nums[i - 1] % 3 == 1) {
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            } else if (nums[i - 1] % 3 == 2) {
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }
        return dp[n][0];
    }
};
*/

// 距离相等的条形码
/*
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = static_cast<int>(barcodes.size());
        // 统计每个元素的数量
        std::unordered_map<int,int> hash;
        int mcount = 0;
        int mval = 0;
        for(auto e : barcodes) {
            ++hash[e];
            // 更新最多数量元素的值
            if(hash[e] > mcount) {
                mcount = hash[e];
                mval = e;
            }
        }

        hash.erase(mval);
        std::vector<int> res(n);
        int pos = 0;

        // 先将最多数量的元素隔行放置
        while(mcount--) {
            res[pos] = mval;
            pos += 2;
        }

        for(auto &[v,c] : hash) {
            // 再将剩余的元素放置
            while(c--) {
                if(pos >= n) {
                    pos = 1;
                }
                res[pos] = v;
                pos += 2;
            }
        }
        return res;
    }
};
*/

// 重构字符串
/*
string reorganizeString(string s) {

        int n = static_cast<int>(s.size());

        int hash[26] { 0 };
        int maxcount = 0; char maxchar = ' ';
        for(auto ch : s) {
            if(maxcount < ++hash[ch - 'a']) {
                maxcount = hash[ch - 'a'];
                maxchar = ch;
            }
        }

        if(maxcount > (n + 1) / 2) {
            return "";
        }

        hash[maxchar - 'a'] = 0; int pos = 0;
        std::string ans; ans.resize(n,' ');

        while(maxcount--) {
            ans[pos] = maxchar;
            pos += 2;
        }

        for(int i = 0; i < 26; ++i) {
            while(hash[i]--) {
                if(pos >= n) {
                    pos = 1;
                }
                ans[pos] = i + 'a';
                pos += 2;
            }
        }

        return ans;
    }
*/

// 删除字符串中的所有相邻重复项
/*
string removeDuplicates(string s) {
        std::string st;
        for(auto ch : s) {

            // 遇到相同的字母就消除
            if(!st.empty() && st.back() == ch) {
                st.pop_back();
            } else {
                st.push_back(ch);
            }

            // if(st.empty()) {
            //     st.push_back(ch);
            // } else {
            //     if(st.back() == ch) {
            //         st.pop_back();
            //     } else {
            //         st.push_back(ch);
            //     }
            // }
        }
        return st;
    }
*/

// 比较含退格的字符串
/*
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return str2Text(s) == str2Text(t);
    }

    std::string str2Text(std::string &str) {
        std::string text;

        for(auto ch : str) {
            if(ch == '#') {
                if(!text.empty()) {
                    text.pop_back();
                }
                continue;
            }
            text.push_back(ch);
        }

        return text;
    }
};
*/

// 无括号基本计算
/*
int calculate(string s) {
        char op = '+';
        std::vector<int> st;

        int n = static_cast<int>(s.size());
        for(int i = 0; i < n;) {
            if(s[i]==' ') {
                i++;
            } else if(std::isalnum(s[i])) {
                int pos = i;
                // 提取数字
                while(pos < n && std::isalnum(s[pos])) {
                    ++pos;
                }

                int num = std::atoi(s.substr(i,pos - i).c_str());

                switch(op) {
                    case '-':
                        st.push_back(-num);
                        break;
                    case '+':
                        st.push_back(num);
                        break;
                    case '*':
                        st.back() *= num;
                        break;
                    case '/':
                        st.back() /= num;
                        break;
                }
                i = pos;
            } else {
                op = s[i];
                ++i;
            }
        }
        return accumulate(st.begin(), st.end(), 0);
    }
*/

// 字符串解码
/*
string decodeString(string s) {
        std::stack<int> nums;
        std::stack<std::string> strs;
        strs.push("");

        int i = 0;
        int n = static_cast<int>(s.size());

        while(i < n) {
            if(s[i] >='0' && s[i] <= '9') { // 提取整个数字
                int num = 0;
                while(i < n && s[i] >='0' && s[i] <= '9') {
                    num = num * 10 + (s[i] - '0');
                    ++i;
                }
                nums.push(num);
            } else if(s[i] == '[') { // 把括号后⾯的字符串提取出来
                ++i;
                std::string str;
                while(i < n && s[i] >='a' && s[i] <= 'z') {
                    str += s[i];
                    ++i;
                }
                strs.push(str);
            } else if(s[i] == ']') {
                int num = nums.top();
                nums.pop();
                std::string str = strs.top();
                strs.pop();

                while(num--) {
                    strs.top() += str;
                }
                ++i;
            } else { // 单个字符直接追加
                strs.top() += s[i];
                ++i;
            }
        }
        return strs.top();
    }
*/

// 冶炼金属
/*
#include <iostream>
using namespace std;

const int N_MAX = 1e4 + 10;
int N;

int A[N_MAX];
int B[N_MAX];

bool checkL(int v) {
    for(int i = 0; i < N; ++i) {
        if(A[i] / v > B[i]) {
            return false;
        }
    }
    return true;
}

bool checkR(int v) {
    for(int i = 0; i < N; ++i) {
        if(A[i] / B[i] < v) {
            return false;
        }
    }
    return true;
}

int main() {

    std::cin>>N;

    for(int i = 0; i < N; ++i) {
        std::cin>>A[i]>>B[i];
    }

    int l = 1;
    int r = 1e9;
    // 找左端点
    while(l < r) {

        int mid = l + ((r - l) >> 1);

        if(checkL(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }

    }

    std::cout<<l<<" ";

    l = 1;
    r = 1e9;
    // 找右端点
    while(l < r) {

        int mid = l + ((r - l + 1) >> 1);

        if(checkR(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }

    }
    std::cout<<l<<std::endl;

    return 0;
}
*/

// 验证栈序列
/*
  bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n = static_cast<int>(popped.size());
        std::stack<int> st;
        int i = 0;
        for(int e : pushed) {
            st.push(e);

            while(!st.empty() && st.top() == popped[i]) {
                st.pop();
                ++i;
            }
        }
        return i == n;
    }
*/

//#include <iostream>
//#include <cstdio>
//#include <Windows.h>
// 一：
// 因为C++兼容C，所以iostream IO与 stdio IO需要保持同步,也就是共用一块缓冲区
//      并且C的输入输出优先于C++的输入输出，如果需要取消同步流可以：sync_with_stdio(false)
/*
    // 同步：
    stdio IO  ->
                    C流缓冲区（需要保证线程安全）
    iostream IO -> 

    // 异步：
    stdio IO  ->     C流缓冲区
                                 （取消同步后，io函数不能混用）
    iostream IO ->   C++流缓冲区
*/
// 二：
// 三类缓冲机制
//  1. 全缓冲 : 只有缓冲区满了才进行io
//  2. 行缓冲 : 遇到\n 或者 缓冲区满了才进行io
//  3. 无缓冲 : 无条件io,
// cout除了行缓冲，flush()外还有一种刷新缓冲区的策略，也就是当cin读取输入时则会刷新cout缓冲区
// 如何取消这一策略：cout.tie(0) 解除绑定
// 三：
// std::endl = \n + 强制刷新缓冲区
/*
template <class _Elem, class _Traits>
basic_ostream<_Elem, _Traits>& __CLRCALL_OR_CDECL endl(
    basic_ostream<_Elem, _Traits>& _Ostr) { // insert newline and flush stream
    _Ostr.put(_Ostr.widen('\n'));
    _Ostr.flush();
    return _Ostr;
}
*/

// 接龙数列
/*
#include <iostream>
using namespace std;

const int MAX_N = 1e5+10;
int N;
int A[MAX_N];
// 建表
int dp[MAX_N];

int main() {

    std::ios::sync_with_stdio(false); std::cin.tie(0);

    std::cin>>N;

    for(int i = 0; i < N; ++i) {
        int head;
        std::cin>>head;
        // 获取数字的首和尾
        int tail = head % 10;
        while(head > 10) {
            head /= 10;
        }

        A[i] = head * 10 + tail;
        // 初始化dp表
        dp[i] = 1;
    }

    // 状态表示dp[i]: 表示以i位置为结尾的最长接龙子数列
    // 状态转移方程: if( A[i][h] == A[j][t] ) dp[i] = max(dp[j] + 1,dp[i])
    int maxlen = 0;
    for(int i = 1; i < N; ++i) {
        for(int j = 0; j < i; ++j) {
            if((A[i] / 10) == (A[j] % 10)) {
                dp[i] = std::max(dp[j] + 1, dp[i]);
            }
            maxlen = std::max(maxlen, dp[i]);
        }

    }
    std::cout<<N - maxlen<<"\n";
    return 0;
}
*/
/*
int main () {
    int n, mx = 0; cin >> n;
    for (int i = 0; i < n; i ++) {
        string s; cin >> s;
        int a = s[0] - '0', b = s.back() - '0';
        dp[b] = max(dp[b], dp[a] + 1), mx = max(mx, dp[b]);
    }
    cout << n - mx << endl;
    return 0;
}
*/

// 二叉树最大宽度
/*
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {

        if(root == nullptr) {
            return 0;
        }

        std::queue<std::pair<TreeNode *,unsigned int>> q;
        q.push({root, 1});

        unsigned int ans = 0;
        while(!q.empty()) {
            int n = static_cast<int>(q.size());

            unsigned int l = q.front().second;
            unsigned int r = q.back().second;
            ans = std::max(ans,r - l + 1);
            for(int i = 0; i < n; ++i) {

                auto hd = q.front();
                q.pop();
                unsigned int pos = hd.second;
                if((hd.first)->left != nullptr) {
                    q.push({(hd.first)->left, 2*pos});
                }

                if((hd.first)->right != nullptr) {
                    q.push({(hd.first)->right, 2*pos + 1});
                }
            }
        }
        return ans;
    }
};
*/

// 在每个树行中找最大值
/*
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(root == nullptr) {
            return {};
        }

        std::queue<TreeNode *> q;
        std::vector<int> ret;
        q.push(root);

        while(!q.empty()) {
            int n = static_cast<int>(q.size());

            int ans = INT_MIN;
            for(int i = 0; i < n; ++i) {

                auto hd = q.front();
                q.pop();
                // 更新每层最大值
                ans = std::max(ans,hd->val);

                if(hd->left != nullptr) {
                    q.push(hd->left);
                }

                if(hd->right != nullptr) {
                    q.push(hd->right);
                }
            }
            ret.push_back(ans);
        }
        return ret;
    }
};
*/

// N 叉树的层序遍历
/*
vector<vector<int>> levelOrder(Node* root) {
        if(root == nullptr) {
            return {};
        }

        std::queue<Node *> q;
        std::vector<std::vector<int>> result;
        q.push(root);

        while(!q.empty()) {
            int n = static_cast<int>(q.size());

            std::vector<int> ret;
            for(int i = 0; i < n; ++i) {

                auto hd = q.front();
                q.pop();
                ret.push_back(hd->val);

                for(auto node : hd->children) {
                    if(node != nullptr) {
                        q.push(node);
                    }
                }

            }
            result.push_back(ret);
        }
        return result;
    }
*/

// 数据流中的第 K 大元素
/*
class KthLargest {
public:
    std::priority_queue<int,std::vector<int>,std::greater<int>> hp;
    int k;
    KthLargest(int _k, vector<int>& nums) :k(_k) {
        for(auto e : nums) {
            hp.push(e);

            if(static_cast<int>(hp.size()) > k) {
                hp.pop();
            }
        }
    }

    int add(int val) {

        hp.push(val);

        if(static_cast<int>(hp.size()) > k) {
                hp.pop();
        }
        return hp.top();
    }
};
*/

// 前K个高频单词
/*
using PSI = std::pair<std::string, int>;
    vector<string> topKFrequent(vector<string>& words, int k) {

        // 先统计字符串对应的个数
        std::unordered_map<std::string, int> hash;
        for(auto &word : words) {
            ++hash[word];
        }

        // k大小的频率小堆 & 字典序大堆
        auto cmp = [](const PSI & p1, const PSI & p2){
            if(p1.second == p2.second) {
                return p1.first < p2.first;
            } else {
                return p1.second > p2.second;
            }
        };

        std::priority_queue<PSI,std::vector<PSI>,decltype(cmp)> hp(cmp);

        for(auto p : hash) {
            hp.push(p);

            if(hp.size() > k) {
                hp.pop();
            }
        }

        std::vector<std::string> ret(k);

        for(int i = k - 1; i >= 0; --i) {
            ret[i] = (hp.top().first);
            hp.pop();
        }

        return ret;
    }
*/

// 数据流的中位数
/*
class MedianFinder {
    // 大堆
    std::priority_queue<int, std::vector<int>, std::less<int>> left;
    // 小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> right;
public:
    MedianFinder() = default;

    void addNum(int num) {
        int l = static_cast<int>(left.size());
        int r = static_cast<int>(right.size());
        if(l == r) {
            if(left.empty() || num <= left.top()) { // 左右两个堆的元素个数相同
                left.push(num);
            } else {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        } else {
            if(num <= left.top()) {
                left.push(num);
                right.push(left.top());
                left.pop();
            } else {
                right.push(num);
            }
        }
    }

    double findMedian() {
        int l = static_cast<int>(left.size());
        int r = static_cast<int>(right.size());
        // 保持l >= r
        if(l == r) {
            return (left.top() + right.top()) / 2.0;
        } else {
            return left.top();
        }
    }
};
*/

//bfs
/*
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        int pcolor = image[sr][sc];
        int m = static_cast<int>(image.size());
        int n = static_cast<int>(image.back().size());
        if(pcolor == color) {
            return image;
        }
        int dx[] = {0,0,-1,1};
        int dy[] = {-1,1,0,0};

        std::queue<std::pair<int,int>> q;
        q.push({sr,sc});
        image[sr][sc] = color;

        while(!q.empty()) {

            auto [a,b] = q.front();
            q.pop();

            for(int i = 0; i < 4; ++i) {
                int x = dx[i] + a;
                int y = dy[i] + b;
                if(x>=0 && x<m && y>=0 && y<n && image[x][y] == pcolor) {
                    q.push({x,y});
                    image[x][y] = color;
                }
            }
        }
        return image;
    }
};
*/

// 迷宫中离入口最近的出口
/*
class Solution {
public:
    int dx[4]{0,0,-1,1};
    int dy[4]{-1,1,0,0};

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {

        int nr = maze.size();
        int nc = maze.size();

        std::vector<std::vector<bool>> vis(nr,std::vector<bool>(nc,false));
        std::queue<std::pair<int,int>> q;

        q.push({entrance.front(),entrance.back()});
        vis[entrance.front()][entrance.back()] = true;

        int ret = 0;
        while(!q.empty()) {

            int n = static_cast<int>(q.size());

            for(int i = 0; i < n; ++i) {

                auto [a,b] = q.front();
                q.pop();
                ret++;

                for(int z = 0; z < 4; ++z) {

                    int x = dx[z] + a;
                    int y = dy[z] + b;

                    if(x>=0 && x<nr && y>=0 && y<=nc && maze[x][y] != '+' && !vis[x][y]) {

                        if(x == 0 || x == nr - 1 || y == 0 || y == nc - 1) {
                            return ret;
                        }

                        q.push({x,y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};
*/

// 最小基因变化 -- 边权值为一的最短路问题
/*
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {

        // 快速判断变化基因是否有效
        std::unordered_set<std::string> dict;
        for(auto &str : bank) {
            dict.insert(str);
        }

        const char* change = "ACGT";
        std::queue<std::string> q;
        std::unordered_set<std::string> vis;

        q.push(startGene);
        vis.insert(startGene);

        int ans = 0;
        while(!q.empty()) {

            int n = static_cast<int>(q.size());
            ans++;
            while(n--) {

                auto str = q.front();
                q.pop();

                // 枚举每一个位置进行变化
                for(int i = 0; i < 8; ++i) {

                    for(int j = 0; j < 4; ++j) {

                        std::string tmp = str;
                        tmp[i] = change[j];
                        // 判断是否被访问过 & 是否在基因库中
                        if(!vis.count(tmp) && dict.count(tmp)) {

                            if(tmp == endGene) {
                                return ans;
                            }
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};
*/

// 单词接龙
/*
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        std::unordered_set<std::string> hash;
        for(auto &str : wordList) {
            hash.insert(str);
        }

        if(!hash.count(endWord)) {
            return 0;
        }

        std::queue<std::string> que;
        std::unordered_set<std::string> vis;

        que.push(beginWord);
        vis.insert(beginWord);

        int ans = 1;
        while(!que.empty()) {

            int n = static_cast<int>(que.size());
            ++ans;

            while(n--) {

                std::string str = que.front();
                que.pop();

                for(int i = 0; i < str.size(); ++i) {
                    // std::string tmp = str;
                    for(char ch = 'a'; ch <= 'z'; ++ch) {

                        std::string tmp = str;
                        tmp[i] = ch;

                        if(hash.count(tmp) && !vis.count(tmp)) {
                            if(tmp == endWord) {
                                return ans;
                            }
                            que.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};
*/

// 比赛砍树
/*
class Solution {
public:
    // struct Entry {
    // public:
    //     int x;
    //     int y;
    // };
    #define X first
    #define Y second
    bool visited[55][55];

    int dx[4]{0,0,-1,1};
    int dy[4]{-1,1,0,0};

    int bfs(int bx, int by, int ex, int ey, const vector<vector<int>>& forest) {

        if(bx == ex && by == ey) {
            return 0; // 可能(0,0)位置就有树木
        }

        int nr = forest.size();
        int nc = forest.back().size();

        // 初始化
        std::memset(visited, 0 ,sizeof(visited));

        std::queue<std::pair<int, int>> q;
        q.push({bx,by});
        visited[bx][by] = true;

        int step = 0;
        while(!q.empty()) {

            int n = static_cast<int>(q.size());
            step++;
            while(n--) {

                auto [r,c] = q.front();
                q.pop();

                for(int z = 0; z < 4; ++z) {

                    int x = dx[z] + r;
                    int y = dy[z] + c;
                    if(x>=0 && x<nr && y>=0 && y<nc && !visited[x][y] && forest[x][y] != 0) {
                        if(x==ex && y==ey) {
                            return step;
                        }
                        q.push(std::pair<int,int>(x,y));
                        visited[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) {

        int nr = forest.size();
        int nc = forest.back().size();

        auto cmp = [&](const std::pair<int,int> &p1, const std::pair<int,int> &p2){
            return forest[p1.X][p1.Y] < forest[p2.X][p2.Y];
        };

        // 按照树的高度保存树木的位置
        std::set<std::pair<int,int>,decltype(cmp)> pairs(cmp);
        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {
                if(forest[i][j] > 1) {
                    pairs.insert(std::make_pair(i,j));
                }
            }
        }

        int bx = 0;
        int by = 0;
        int dist = 0;
        // 计算相邻点的最短距离
        for(auto & p : pairs) {
            int ex = p.X;
            int ey = p.Y;

            int ret = bfs(bx,by,ex,ey,forest);

            if(ret == -1) {
                return ret;
            }

            dist += ret;

            bx = ex;
            by = ey;
        }

        return dist;
    }
};
*/

// 01 矩阵
/*
class Solution
{
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        int nr = static_cast<int>(mat.size());
        int nc = static_cast<int>(mat.back().size());

        // 创建一个与mat相同大小的矩阵，并全部初始化为-1表示被未访问过
        std::vector<std::vector<int>> ret(nr, std::vector<int>(nc,-1));

        // 将值为0的坐标入队
        std::queue<std::pair<int, int>> q;
        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {

                if(mat[i][j] == 0) {
                    q.push({i,j});
                    ret[i][j] = 0;
                }
            }
        }

        int dx[4]{0,0,-1,1};
        int dy[4]{-1,1,0,0};

        // 多源bfs最短路
        while(!q.empty()) {

            // 一层一层的出队
            int n = static_cast<int>(q.size());
            while(n--) {

                auto [a,b] = q.front();
                q.pop();

                for(int z = 0; z < 4; ++z) {

                    int x = dx[z] + a;
                    int y = dy[z] + b;
                    // 下标合法，并且该位置没有被访问过
                    if(x>=0 && x < nr && y>=0 && y<nc && ret[x][y] == -1) {
                        q.push({x,y});
                        ret[x][y] = ret[a][b] + 1; // 相邻位置距离加一
                    }
                }
            }
        }
        return ret;
    }
};
*/

// N皇后
/*
class Solution {
public:
    std::vector<std::vector<std::string>> result;
    std::vector<std::string> matrix;
    std::vector<bool> vrow;
    std::vector<bool> vcol;
    std::vector<bool> vld;
    std::vector<bool> vcd;

    void dfs(int x, int y, int n, int s) {

        if(y == n) {
            y = 0;
            x++;
        }

        if(x == n) {
            if(s == n) {
                result.push_back(matrix);
            }
            return;
        }

        // 放
        if(!vrow[x] && !vcol[y] && !vld[x-y+n] && !vcd[x+y]) {
            matrix[x][y] = 'Q';
            vrow[x]=true;
            vcol[y]=true;
            vld[x-y+n]=true;
            vcd[x+y]=true;

            dfs(x, y+1, n, s + 1);

            matrix[x][y] = '.';
            vrow[x]=false;
            vcol[y]=false;
            vld[x-y+n]=false;
            vcd[x+y]=false;
        }

        // 不放
        dfs(x, y + 1, n, s);
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vrow=std::vector<bool>(n,false);
        vcol=std::vector<bool>(n,false);
        vld=std::vector<bool>(2*n - 1,false);
        vcd=std::vector<bool>(2*n - 1,false);
        matrix=std::vector<std::string>(n,std::string(n,'.'));
        dfs(0,0,n,0);
        return result;
    }
};
*/

// 飞地的数量
/*
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {

        int nr = static_cast<int>(grid.size());
        int nc = static_cast<int>(grid.back().size());

        std::queue<std::pair<int, int>> q;

        // 将首列及尾列为一的下标入队
        for(int i = 0; i < nr; ++i) {

            if(grid[i][0] == 1) {
                grid[i][0] = -1; // 标记访问过
                q.push({i,0});
            }
            if(grid[i][nc-1] == 1) {
                grid[i][nc-1] = -1;
                q.push({i,nc-1});
            }
        }

        // 将首行及尾行为一的下标入队
        for(int j = 0; j < nc; ++j) {

            if(grid[0][j] == 1) {
                grid[0][j] = -1;
                q.push({0,j});
            }
            if(grid[nr-1][j] == 1) {
                grid[nr-1][j] = -1;
                q.push({nr-1,j});
            }
        }

        int dx[4]{0,0,-1,1};
        int dy[4]{-1,1,0,0};

        while(!q.empty()) {

            auto [a,b] = q.front();
            q.pop();

            for(int k = 0; k < 4; ++k) {
                int x = dx[k] + a;
                int y = dy[k] + b;

                if(x>=0 && x<nr && y>=0 && y<nc && grid[x][y] == 1) {
                    q.push({x,y});
                    grid[x][y] = -1;
                }
            }
        }

        int ans = 0; // 统计还有多少个一
        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {
                if(grid[i][j] == 1) {
                    ans++;
                }
            }
        }

        return ans;
    }
};
*/

// K 个元素的最大和
/*
 int maximizeSum(vector<int>& nums, int k) {
        int maxval = *std::max_element(nums.begin(),nums.end());

        return (maxval + maxval + k - 1) * k / 2;
        // int sum = 0;
        // while(k--) {
        //     sum += maxval;
        //     ++maxval;
        // }
        // return sum;
    }
*/

// 最长奇偶子数组
/*
class Solution {
public:
    // 状态表示：
    // f[i]: 表示以i位置为结尾 && nums[i]%2==0 的最长奇偶子数组
    // g[i]: 表示以i位置为结尾 && nums[i]%2==1 的最长奇偶子数组
    // 状态转移方程：
    // 如果nums[i]为偶数 && nums[i] < threshold 则 f[i] = g[i-1] + 1 否则f[i] = 0
    // 如果nums[i]为奇数 && nums[i] < threshold  && f[i-1] != 0 则 g[i] = f[i-1] + 1 否则g[i] = 0
    // 初始化：f[i] = g[i] = 0 遍历顺序：左到右 返回结果：max(f[i],g[i])
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {

        // 建表
        int n = static_cast<int>(nums.size());
        std::vector<int> f(n + 1, 0);
        auto g = f;

        // 填表
        for(int i = 1; i <= n; ++i) {
            // 注意下标映射
            if(nums[i-1] > threshold) {
                f[i] = g[i] = 0;
                continue;
            }

            if(nums[i-1] % 2 == 0) {
                f[i] = g[i-1] + 1;
            } else {
                if(f[i-1] != 0) {
                    g[i] = f[i-1] + 1;
                }
            }
        }

        // 返回结果
        return std::max(*std::max_element(f.begin(),f.end()),
                        *std::max_element(g.begin(),g.end()));
    }
};
*/
/*
int longestAlternatingSubarray(vector<int> &nums, int threshold) {
        int n = static_cast<int>(nums.size());
        int ans = 0; int i = 0;
        while (i < n) {
            if (nums[i] > threshold || nums[i] % 2 == 1) {
                i++; // 直接跳过
                continue;
            }
            int start = i++; // 记录这一组的开始位置, 开始位置已经满足要求, 从下一个位置开始判断
            while (i < n && nums[i] <= threshold && nums[i - 1] % 2 != nums[i] % 2) {
                i++;
            }
            // 从 start 到 i-1 是满足题目要求的子数组
            ans = max(ans, i - start);
        }
        return ans;
    }
*/

// 地图中的最高点 
/*
class Solution {
public:
    // 多源bfs：陆地高度为与水域的距离
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int nr = static_cast<int>(isWater.size());
        int nc = static_cast<int>(isWater.back().size());

        auto ret = isWater;
        ret.clear();
        ret.resize(nr,std::vector<int>(nc,-1));

        // 将水域单元格坐标入队
        std::queue<std::pair<int, int>> q;
        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {
                if(isWater[i][j] == 1) {
                    q.push({i,j});
                    ret[i][j] = 0;
                }
            }
        }

        int dx[4]{0,0,-1,1};
        int dy[4]{-1,1,0,0};

        while(!q.empty()) {

            int n = static_cast<int>(q.size());
            while(n--) {

                auto [a, b] = q.front();
                q.pop();

                for(int z = 0; z < 4; ++z) {
                    int x = dx[z] + a;
                    int y = dy[z] + b;
                    if(x>=0 && x<nr && y>=0 && y<nc && ret[x][y] == -1) {
                        q.push({x,y});
                        ret[x][y] = ret[a][b] + 1;
                    }
                }
            }
        }
        return ret;
    }
};
*/

// 最长连续序列
/*
 int longestConsecutive(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
        int ans = 0;
        int i = 0;
        int n = static_cast<int>(nums.size());
        while(i < n) {

            int start = i++;
            while(i < n && nums[i] - nums[i-1] == 1 ) {
                i++;
            }
            ans = std::max(ans,i - start);
        }
        return ans;
    }
*/

// 课程表
/*
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 邻接表
        std::vector<std::vector<int>> edges(numCourses);
        // 记录每一个顶点的入度
        std::vector<int> ind(numCourses,0);
        for(auto &v : prerequisites) {
            int a = v.front();
            int b = v.back();
            // b ---> a
            edges[b].push_back(a);
            ind[a]++;
        }

        std::queue<int> q;
        for(int i = 0; i < numCourses; ++i) {
            // 将度为0的顶点入队
            if(ind[i] == 0) {
                q.push(i);
            }
        }

        while(!q.empty()) {

            auto hd = q.front();
            q.pop();

            for(auto &e : edges[hd]) {
                // 将与hd相连顶点的入度减一
                ind[e]--;
                if(ind[e] == 0) {
                    q.push(e);
                }
            }
        }

        for(int i = 0; i < numCourses; ++i) {
            // 如果还有入度为非零的顶点则返回false
            if(ind[i] != 0) {
                return false;
            }
        }
        return true;
    }
*/

// 课程表 IV
/*
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {

        std::unordered_map<int,std::vector<int>> edges; // 邻接表
        std::vector<int> indg(numCourses); // 入度表
        for(auto & v : prerequisites) {
            // [a ---> b]
            int a = v.front();
            int b = v.back();
            edges[a].push_back(b);
            indg[b]++;
        }

        std::queue<int> q;
        for(int i = 0; i < numCourses; ++i) {
            // 将度为0的顶点入队
            if(indg[i] == 0) {
                q.push(i);
            }
        }

        std::vector<std::vector<bool>> ispre(numCourses,std::vector<bool>(numCourses,false));
        while(!q.empty()) {

            auto hd = q.front();
            q.pop();

            for(auto &e : edges[hd]) {
                ispre[hd][e] = true;
                for (int i = 0; i < numCourses; ++i) {
                    ispre[i][e] = ispre[i][e] | ispre[i][hd]; // i ---> hd ---> e
                }
                // 将与hd相连顶点的入度减一
                indg[e]--;
                if(indg[e] == 0) {
                    q.push(e);
                }
            }
        }
        std::vector<bool> result;
        for(auto &v : queries) {
           result.push_back(ispre[v[0]][v[1]]);
        }

        return result;
    }
*/

// 数位和相等数对的最大和
/*
class Solution {
public:
    int getDigitalSum(int num) {
        int sum = 0;
        while(num > 0) {
            sum += (num%10);
            num /= 10;
        }
        return sum;
    }
    int maximumSum(vector<int>& nums) {

        // key：数位和 value：该数位和的最大值
        std::unordered_map<int, int> hash;

        int ans = -1;
        for(auto e : nums) {

            int digit = getDigitalSum(e);

            if(hash.find(digit) == hash.end()) {
                hash[digit] = e;
            } else {
                // 更新答案
                ans = std::max(ans, hash[digit] + e);
                // 更新该位数和对应的最大值
                hash[digit] = std::max(hash[digit],e);
            }
        }
        return ans;
    }
};
*/

// 火星词典 
/*
class Solution {
public:
    string alienOrder(vector<string>& words) {
        int n = static_cast<int>(words.size());
        // 邻接表
        std::unordered_map<char,unordered_set<char>> hash;
        // 入度表
        std::unordered_map<char,int> indg;

        for(int i = 0; i < n; ++i) {
            for(auto ch : words[i]) {
                indg[ch] = 0;
            }
        }

        for(int j = 0; j < n; ++j) {

            for(int i = j + 1; i < n; ++i) {

                std::string &s1 = words[j];
                std::string &s2 = words[i];
                // int pos = 0;
                // int sz = std::min(s1.size(),s2.size());
                // while(pos < sz) {

                //     if(s1[pos] != s2[pos]) {
                //         if(hash.count(s1[pos]) == 0 || hash[s1[pos]].find(s2[pos]) == hash[s1[pos]].end()) {
                //             hash[s1[pos]].insert(s2[pos]);
                //             indg[s2[pos]]++;
                //         }
                //         break;
                //     }

                //     pos++;
                // }
                // if(pos == s2.size() && pos < s1.size()) {
                //     return "";
                // }
                int l1 = 0;
                int l2 = 0;
                int r1 = static_cast<int>(s1.size());
                int r2 = static_cast<int>(s2.size());

                while(l1 < r1 && l2 < r2) {
                    if(s1[l1] != s2[l2]) {
                        // s1[l1] < s2[l2] : s1[l1] ---> s2[l2]
                        // 避免重复
                        // if(hash[s1[l1]].find(s2[l2]) == hash[s1[l1]].end()) {
                        //     hash[s1[l1]].insert(s2[l2]);
                        //     indg[s2[l2]]++;
                        // }
                        if(!hash.count(s1[l1]) || hash[s1[l1]].find(s2[l2]) == hash[s1[l1]].end()) {
                            hash[s1[l1]].insert(s2[l2]);
                            indg[s2[l2]]++;

                        }
                        break;
                    }
                    l1++;
                    l2++;
                }

                if(l2 == r2 && l1 < r1) {
                    return "";
                }
            }
        }

        // 将入度为零的顶点入队
        std::queue<char> q;
        for(auto & p : indg) {
            if(p.second == 0) {
                q.push(p.first);
            }
        }

        std::string result;
        while(!q.empty()) {
            char hd = q.front();
            result += hd;
            q.pop();
            for(auto e : hash[hd]) {
                indg[e]--;
                if(indg[e] == 0) {
                    q.push(e);
                }
            }
        }
        for(auto& [a, b] : indg) {
            if(b != 0) return "";
        }
        return result;
    }
};
*/

// 找到字符串中所有字母异位词
/*
// 暴力：
vector<int> findAnagrams(string s, string p) {

        std::sort(p.begin(),p.end());
        std::vector<int> ans;

        int ns = static_cast<int>(s.size());
        int np = static_cast<int>(p.size());

        for(int i = 0; i < ns; ++i) {

            std::string tmp = s.substr(i,np);
            std::sort(tmp.begin(),tmp.end());

            if(tmp == p) {
                ans.push_back(i);
            }
        }

        return ans;
    }
*/

// 最小覆盖子串
/*
class Solution {
public:
    string minWindow(string s, string t) {
        std::unordered_map<char, int> need;
        std::unordered_map<char, int> window;

        for(auto ch : t) {
            need[ch]++;
        }

        int left = 0;
        int right = 0;
        int valid = 0;
        int start = 0;
        int len = std::numeric_limits<int>::max();
        int n = static_cast<int>(s.size());

        while(right < n) {

            // 入窗口
            char in = s[right++];
            if(need.find(in) != need.end()) {

                window[in]++;
                if(window[in] == need[in]) {
                    valid++;
                }
            }

            // 出窗口
            while(valid == need.size()) {

                // 更新结果
                if(right - left < len) {
                    start = left;
                    len = right - left;
                }

                char out = s[left++];

                if(need.find(out) != need.end()) {
                    // 出之前比较
                    if(window[out] == need[out]) {
                        valid--;
                    }
                    window[out]--;
                }
            }
        }

        return len == std::numeric_limits<int>::max() ? "" : s.substr(start,len);
    }
};
*/

// 搜索二维矩阵
/*
  bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int nr = static_cast<int>(matrix.size());
        int nc = static_cast<int>(matrix.back().size());

        for(int i = 0; i < nr; ++i) {

            if(matrix[i][nc-1] >= target) {

                for(int j = 0; j < nc; ++j) {
                    if(matrix[i][j] == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
*/

// 环形链表的约瑟夫问题
/*
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10000 + 10;
int pre[MAX_N];
int val[MAX_N];
int nxt[MAX_N];

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int m = 0;

    std::cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        val[i] = i;
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    //   3

    pre[1] = n;
    nxt[n] = 1;

    int cnt = 0;
    int pos = 1;
    while (n > 1) {

        cnt++;
        if (cnt == m) {

            nxt[pre[pos]] = nxt[pos];
            pre[nxt[pos]] = pre[pos];

            // std::cout << val[pos] << " ";

            cnt = 0;
            n--;
        }
        pos = nxt[pos];
    }

    std::cout<<val[pos]<<std::endl;
    return 0;
}
*/

// 树的重心
/*
#include <iostream>
#include <vector>

int n = 0;
int ans = std::numeric_limits<int>::max();
std::vector<std::vector<int>> edges; // 邻接表
std::vector<bool> vis; // 标记是否访问过

int dfs(int u) {

    vis[u] = true; // 记录该点访问过，标记之后还能让每一个点只搜索自己的子树有多少个结点

    int sum = 1; // 表示该树有多少个结点
    int res = 0;

    for(auto & e : edges[u]) {

        if(!vis[e]) {

            int ret = dfs(e);

            sum += ret;

            res = std::max(res, ret);
        }
    }

    res = std::max(res, n - sum); // n - sum 表示双亲结点对应的连通块有多少个点
    ans = std::min(ans, res);

    //std::cout<<res<<" ";

    return sum;
}

int main() {


    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

    std::cin>>n;

    edges.resize(n + 1);
    vis.resize(n + 1, false);

    for(int i = 1; i < n; ++i) {
        int a = 0;
        int b = 0;
        std::cin>>a>>b;

        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    dfs(1);

    std::cout<<ans<<std::endl;

    return 0;
}
*/

// 求连通域
/*
#include <iostream>
#include <vector>
#include <cstdio>
#include <utility>
int M, N;

std::vector<std::vector<int>> mat;

std::vector<std::pair<int, int>> xy;

int dx[8]{ 0,0,-1,1, -1,-1,1,1 };
int dy[8]{ -1,1,0,0, -1,1,1,-1 };

//vector<int> dx = { -1, -1, -1, 0, 0, 1, 1, 1 }; // 8连通域
//vector<int> dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

void dfs(int r, int c) {

    xy.push_back({ r,c });
    mat[r][c] = 0;

    for (int z = 0; z < 8; ++z) {

        int x = dx[z] + r;
        int y = dy[z] + c;
        if (x >= 0 && x < M && y >= 0 && y < N && mat[x][y] == 1) {
            dfs(x, y);
        }
    }
}

std::pair<double, double> getBarycenter(std::vector<std::pair<int, int>>& pairs) {

    double sum1 = 0;
    double sum2 = 0;

    for (auto p : pairs) {
        sum1 += p.first;
        sum2 += p.second;
    }

    return { sum1 / pairs.size(),sum2 / pairs.size() };
}

int main() {

    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

    std::cin >> M >> N;

    mat.resize(M, std::vector<int>(N, 0));

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            std::cin >> mat[i][j];
        }
    }

    std::vector<int> areas;
    std::vector<std::pair<double, double>> barycenters;

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (mat[i][j] == 1) {
                xy.clear();
                dfs(i, j);
                areas.push_back(xy.size());
                barycenters.push_back(getBarycenter(xy));
            }
        }
    }

    int n = areas.size();
    std::cout << n << std::endl;

    for (int i = 0; i < n; ++i) {

        printf("%d %.2lf %.2lf\n", areas[i], barycenters[i].second, barycenters[i].first);
        // std::cout << areas[i] << " " << barycenters[i].first << " " << barycenters[i].second << "\n";

    }

    return 0;
}
*/

// atoi
/*

class Solution {
public:
    int myAtoi(string s) {
        int flag = 0;
        int i = 0;
        while (i < s.size()) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '-') {
                flag = 1;
                i++;
                break;
            } else if (s[i] == '+') {
                flag = 0;
                i++;
                break;
            } else if (!isdigit(s[i])){
                return 0;
            } else {
                break;
            }
        }
        string str;
        while (i < s.size()) {
            if (isdigit(s[i])) {
                str += s[i];
                i++;
            } else {
                break;
            }
        }
        if (str.size() == 0) {
            return 0;
        }
        long num = 0;
        for (auto s : str) {
            num = num * 10 + s - '0';
            if (num >= pow(2,31)) {
                num = pow(2, 31);
                return flag ? -1 * num : num - 1;
            }
        }
        return flag ? -1 * num : num;
    }
};
*/

// HTML 实体解析器
/*
  string entityParser(string text) {

        std::unordered_map<std::string,std::string> hash{
            {"&quot;","\""},
            {"&apos;","\'"},
            {"&amp;","&"},
            {"&gt;",">"},
            {"&lt;","<"},
            {"&frasl;","/"}
        };

        int left = 0;
        std::string result;
        int n = static_cast<int>(text.size());

        while(left < n) {

            if(text[left] == '&') {

                int right = left;
                while(right < n && text[right] != ';') {
                    right++;
                }

                std::string sep = text.substr(left, right - left + 1);
                if(right>= n || hash.find(sep) == hash.end()) {

                } else {
                    result += (hash[sep]);
                    left = right + 1;
                    continue;
                }
            }
            result += text[left];
            left++;
        }
        return result;
    }
*/

// 不含特殊楼层的最大连续楼层数
/*
int maxConsecutive(int bottom, int top, vector<int>& special) {
    
        // 排序：
        std::sort(special.begin(),special.end());
        int n = static_cast<int>(special.size());
        // int ans = 0;
        int ans = std::max(special.front() - bottom, top - special.back());
        for(int i = 1; i < n; ++i) {
            ans = std::max(ans, special[i] - special[i - 1] - 1);
        }

        // ans = std::max(ans, special.front() - bottom);
        // ans = std::max(ans, top - special.back());
        return ans;

        // 暴力：超时
        // std::unordered_set<int> hash(special.begin(), special.end());
        // int pre = 0;
        // int cur = 0;
        // int ans = 0;

        // for(int i = bottom; i <= top; ++i) {

        //     if(hash.count(i) == 1) {
        //         cur = 0;
        //     } else {
        //         cur = pre + 1;
        //     }
        //     ans = std::max(cur,ans);
        //     pre = cur;
        // }

        // return ans;
    }
*/

// 最大间距 
/*
class Solution {
    void _radixSort(vector<int> &nums, int d) {
        std::vector<std::queue<int>> vq(10);

        // 分发
        for(auto e : nums) {
            vq[ e / d % 10].push(e);
        }

        // 回收
        int idx = 0;
        for(auto &q : vq) {
            while(!q.empty()) {
                nums[idx++] = q.front(); q.pop();
            }
        }
    }
public:
    void radixSort(vector<int> &nums) {

        int maxval = *std::max_element(nums.begin(), nums.end());
        int c = 0;
        while(maxval != 0) {
            maxval /= 10;
            ++c;
        }

        int d = 1;
        for(int i = 0; i < c; ++i) {
            _radixSort(nums,d);
            d *= 10;
        }
    }
    int maximumGap(vector<int>& nums) {

        radixSort(nums);

        int ans = 0;
        for(int i = 1; i < nums.size(); ++i) {
            ans = std::max(ans,nums[i]-nums[i-1]);
        }

        return ans;
    }
};
*/

// 统计和小于目标的下标对数目
/*
int countPairs(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());

        int ans = 0;
        for(int l = 0, r = nums.size() - 1; l < r; ) {

            if(nums[l] + nums[r] >= target) {
                r--;
            } else {
                ans += r - l;
                l++;
            }

        }
        return ans;
    }
*/

// 极大极小游戏
/*
int minMaxGame(vector<int>& nums) {

        while(nums.size() != 1) {

            std::vector<int> newnums(nums.size() / 2);

            for(int i = 0; i < newnums.size(); ++i) {

                if(i % 2 == 0) newnums[i] = std::min(nums[2 * i], nums[2 * i + 1]);
                else newnums[i] = std::max(nums[2 * i], nums[2 * i + 1]);
            }
            nums.swap(newnums);
        }

        return nums[0];
    }
*/

// 将标题首字母大写
/*
string capitalizeTitle(string title) {
        int i = 0;
        int n = static_cast<int>(title.size());

        while(i < n) {

            int pos = i;
            while(pos < n && title[pos] != ' ') {
                title[pos] = std::tolower(title[pos]);
                pos++;
            }

            if(pos - i > 2) {
                title[i] = std::toupper(title[i]);
            }
            i = pos + 1;
        }
        return title;
}
*/

// 找出缺失的观测数据
/*
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {

        int m = static_cast<int>(rolls.size());

        int sum = mean * (m + n);

        for(auto e : rolls) {
            sum -= e;
        }

        if(sum < n || sum > 6 * n) {
            return {};
        }

        int ave = sum / n;
        int exp = sum % n;

        std::vector<int> result(n, ave);

        for(int i = 0; i < exp; i++) {
            result[i]++;
        }

        return result;
    }
*/

// 二叉树中的伪回文路径
/*
int ans = 0;
    int cnt[10] = {0};

    void order(TreeNode *root) {

        if(root == nullptr) {
            return;
        }

        cnt[root->val]++;
        if(root->left == nullptr && root->right == nullptr) {
            int flag = 0;
            for(int i = 1; i < 10; ++i) {
                if(cnt[i] % 2 == 1) {
                    flag++;
                }
            }
            if(flag == 0 || flag == 1) {
                ans++;
            }
        }

        order(root->left);
        order(root->right);
        cnt[root->val]--;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        order(root);
        return ans;
    }
*/

//  给Nx3网格图涂色的方案数
/*
int numOfWays(int n) {

        std::vector<std::vector<long long>> dp(n,std::vector<long long>(2,6));
        long long MOD = 1e9 + 7;
        for(int i = 1; i < n; ++i) {
            dp[i][0] = ((dp[i-1][0] * 3 % MOD) + (dp[i-1][1] * 2 % MOD)) % MOD;
            dp[i][1] = ((dp[i-1][0] * 2 % MOD) + (dp[i-1][1] * 2 % MOD)) % MOD;
        }

        return ( dp[n-1][0] + dp[n-1][1] ) % MOD;
    }
*/

// 统计子串中的唯一字符
/*
class Solution {
public:
    int uniqueLetterString(string s) {
        std::vector<std::vector<int>> idx(26,{-1});
        for(int i = 0; i < s.length(); ++i) {
            idx[s[i] - 'A'].push_back(i); // 记录每一个字符对应出现的下标
        }

        int ans = 0;
        for(auto & v : idx) {
            v.push_back(s.length());
            for(int i = 1; i < v.size() - 1; ++i) {
                ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]);
            }
        }
        return ans;
    }
};
*/
/*
    int ans = 0;
    void check(const std::string &substr) {
        std::unordered_map<char, int> hash;
        for(auto ch : substr) {
            hash[ch]++;
        }

        for(auto &[a,b] : hash) {
            if(b == 1) {
                ans++;
            }
        }
    }
    // 暴力
    int uniqueLetterString(string s) {

        int n = static_cast<int>(s.length());

        for(int i = 0; i < n; ++i) {
            for(int j = i; j < n; ++j) {
                check(s.substr(i,j - i + 1));
            }
        }

        return ans;
    }
*/

// 子数组的最小值之和
/*
class Solution {
public:
    const int MOD = 1e9 + 7;
    int sumSubarrayMins(vector<int>& arr) {
        int n = static_cast<int>(arr.size());

        std::stack<int> st;
        std::vector<int> left(n);
        for(int i = 0; i < n; ++i) {

            while(!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }

            if(st.empty()) {
                left[i] = -1;
            } else {
                left[i] = st.top();
            }
            st.push(i);
        }

        st = std::stack<int>();
        std::vector<int> right(n);
        for(int i = n - 1; i >= 0; --i) {

            while(!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }

            if(st.empty()) {
                right[i] = n;
            } else {
                right[i] = st.top();
            }
            st.push(i);
        }

        for(auto e : right) {
            std::cout<<e<<" ";
        }

        long long ans = 0LL;
        for (int i = 0; i < n; ++i)
            ans += (long long) arr[i] * (i - left[i]) * (right[i] - i); // 累加贡献
        return ans % MOD;
    }
};
*/

// 设计前中后队列
/*
class FrontMiddleBackQueue {
public:
    std::deque<int> ldq;
    std::deque<int> rdq;

    FrontMiddleBackQueue() {

    }

    void adjust() {

        if(ldq.size() > rdq.size()) {
            rdq.push_front(ldq.back());
            ldq.pop_back();
        }

        if(1 + ldq.size() < rdq.size()) {
            ldq.push_back(rdq.front());
            rdq.pop_front();
        }
    }

    void pushFront(int val) {

        ldq.push_front(val);
        adjust();
    }

    void pushMiddle(int val) {

        if(ldq.size() == rdq.size()) {
            rdq.push_front(val);
        } else {
            ldq.push_back(val);
        }
    }

    void pushBack(int val) {

        rdq.push_back(val);
        adjust();
    }

    int popFront() {
        if(rdq.empty()) {
            return -1;
        }

        int ret = 0;
        if(ldq.empty()) {
            ret = rdq.front();
            rdq.pop_front();
        } else {
            ret = ldq.front();
            ldq.pop_front();
        }

        adjust();
        return ret;
    }

    int popMiddle() {
        if(rdq.empty()) {
            return -1;
        }

        int ret = 0;
        if(ldq.size() == rdq.size()) {
            ret = ldq.back();
            ldq.pop_back();
        } else {
            ret = rdq.front();
            rdq.pop_front();
        }

        adjust();
        return ret;
    }

    int popBack() {
        if(rdq.empty()) {
            return -1;
        }

        int ret = rdq.back();
        rdq.pop_back();

        adjust();
        return ret;
    }
};
*/
 
// 无限集中的最小数字 可以攻击国王的皇后
/*
class SmallestInfiniteSet {
public:
    int minnum;
    std::set<int> tree;

    SmallestInfiniteSet() :minnum(1) {

    }

    int popSmallest() {

        int ret = 0;
        auto iter = tree.begin();

        if(iter != tree.end() && *iter < minnum) {
            ret = *iter;
            tree.erase(iter);
        } else {
            ret = minnum++;
        }
        return ret;
    }

    void addBack(int num) {
        if(num < minnum) {
            tree.insert(num);
        }
    }
    // int popSmallest() {
    //     if(tree.empty()) {
    //         return minnum++;
    //     }

    //     int ret = 0; auto iter = tree.begin();
    //     if(*iter < minnum) {
    //         ret = *iter;
    //         tree.erase(iter);
    //     } else {
    //         ret = minnum++;
    //     }
    //     return ret;
    // }
};
*/

// 可以攻击国王的皇后
/*
class Solution {
public:
    // 皇后视角
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

        std::vector<std::vector<int>> board(8, std::vector<int>(8,0)); // 0表示空位置

        for(auto &v : queens) {
            board[v[0]][v[1]] = 1; // 1表示皇后
        }
        board[king[0]][king[1]] = 2; // 2 表示国王

        int dx[8]{0, 0, -1, 1, 1, 1, -1, -1};
        int dy[8]{-1, 1, 0, 0, -1, 1, 1, -1};

        auto result = board; result.clear();
        for(auto &v : queens) {

            int r = v[0]; int c = v[1];

            for(int z = 0; z < 8; ++z) {

                int x = r + dx[z];
                int y = c + dy[z];

                // while(x >= 0 && x < 8 && y >= 0 && y < 8) {

                //     if(board[x][y] == 1) {
                //         break;
                //     } else if(board[x][y] == 2) {
                //         result.push_back({r, c});
                //         break;
                //     }

                //     x += dx[z];
                //     y += dy[z];
                // }


                while(x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 0) {
                    x = x + dx[z];
                    y = y + dy[z];
                }

                if(x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 2) {
                    result.push_back({r, c});
                }
            }
        }

        return result;
    }
};
*/
/*
// 国王视角
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

        std::vector<std::vector<int>> board(8, std::vector<int>(8,0)); // 0表示空位置

        for(auto &v : queens) {
            board[v[0]][v[1]] = 1; // 1表示皇后
        }
        board[king[0]][king[1]] = 2; // 2 表示国王

        int dx[8]{0, 0, -1, 1, 1, 1, -1, -1};
        int dy[8]{-1, 1, 0, 0, -1, 1, 1, -1};

        auto result = board; result.clear();
        int r = king[0]; int c = king[1];
        for(int z = 0; z < 8; ++z) {

            int x = r + dx[z];
            int y = c + dy[z];

            while(x >= 0 && x < 8 && y >= 0 && y < 8) {

                if(board[x][y] == 1) {
                    result.push_back({x, y});
                    break;
                }

                x += dx[z];
                y += dy[z];
            }

        }
        return result;
    }
*/

// 确定两个字符串是否接近 
/*
class Solution {
public:
    bool closeStrings(string word1, string word2) {

        if(word1.size() != word2.size()) {
            return false;
        }

        int arr1[26] = { 0 }; int arr2[26] = { 0 };
        for(auto ch : word1) {
            arr1[ch - 'a']++;
        }
        for(auto ch : word2) {
            arr2[ch - 'a']++;
        }

        for(int i = 0; i < 26; ++i) {
            if(arr1[i] == 0 && arr2[i] == 0) {
                continue;
            }
            if(arr1[i] == 0 || arr2[i] == 0) {
                return false;
            }
        }

        std::sort(arr1,arr1+26);
        std::sort(arr2,arr2+26);
        for(int i = 0; i < 26; ++i) {
            if(arr1[i] != arr2[i]) {
                return false;
            }
        }

        return true;
    }
};
*/

// 设计自助结算系统
/*
class Checkout {
public:
    std::queue<int> nor;
    std::deque<int> max;

    Checkout() {

    }

    int get_max() {
        if(nor.empty()) {
            return -1;
        }
        return max.front();
    }

    void add(int value) {

        nor.push(value);

        while(!max.empty() && max.back() < value) {
            max.pop_back();
        }
        max.push_back(value);
    }

    int remove() {
        if(nor.empty()) {
            return -1;
        }

        int ret = nor.front();
        nor.pop();

        if(max.front() == ret) {
            max.pop_front();
        }
        return ret;
    }
};
*/

// 找出叠涂元素
/*
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {

        int nr = mat.size();
        int nc = mat.back().size();

        std::unordered_map<int,std::pair<int, int>> hash;

        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {

                hash[mat[i][j]] = {i,j}; // 值与下标映射
            }
        }

        std::vector<int> row(nr,nc);
        std::vector<int> col(nc,nr);

        for(int i = 0; i < arr.size(); ++i) {

            auto [a, b] = hash[arr[i]];

            row[a]--;
            col[b]--;
            if(row[a] == 0 || col[b] == 0) {
                return i;
            }
        }

        return -1;
    }
};
*/

// 拼车
/*
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {

        // int allt[1001] = { 0 };
        // for(int i = 0; i < trips.size(); ++i) {
        //     for(int j = trips[i][1]; j < trips[i][2]; ++j) {
        //         allt[j] += trips[i][0];
        //         if(allt[j] > capacity) {
        //             return false;
        //         }
        //     }
        // }

        int n = static_cast<int>(trips.size());

        int nums[1001]{ 0 };
        for(int i = 0; i < n; ++i) {
            int from = trips[i][1];
            int to = trips[i][2];
            nums[from] -= trips[i][0];
            nums[to] += trips[i][0];
        }

        for(int i = 0; i < 1001; ++i) {
            capacity += nums[i];
            if(capacity < 0) {
                return false;
            }
        }

        return true;
    }
};
*/

// 可获得的最大点数
/*
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {

        int n = static_cast<int>(cardPoints.size());

        int m = n - k;
        int sum = 0;
        int minsum = 0x3f3f3f3f;
        for(int l = 0, r = 0; r < n;) {
            // [1,2,3,4,5,6,1]
            while(r < n && r - l < m) {
                sum += cardPoints[r++];
            }

            minsum = std::min(minsum, sum);
            sum -= cardPoints[l++];
        }

        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minsum;
    }
};
*/


// 大小为 K 且平均值大于等于阈值的子数组数目
/*
int numOfSubarrays(vector<int>& arr, int k, int threshold) {

        int n = static_cast<int>(arr.size());
        int ans = 0;
        int sum = 0;
        for(int l = 0, r = 0; r < n; ) {

            while(r < n && r - l < k) {
                sum += arr[r++];
            }

            if(sum / k >= threshold) {
                ans++;
            }
            sum -= arr[l++];
        }
        return ans;
    }
*/

// 从二叉搜索树到更大和树
/*
    int dfs(TreeNode *root, int prevval) {
        if(nullptr == root) {
            return 0;
        }

        // 先处理右子树并获取该右子树所有结点的和
        int r = dfs(root->right, prevval);

        int m = root->val;
        // 将该结点的值替换成树中大于或者等于该节点值的所有节点值之和
        // 也就是右子树区域值和 + 双亲结点区域和 + 本结点值
        root->val = r + prevval + m;
        prevval = root->val;

        int l = dfs(root->left, prevval);

        return r + m + l;
    }

    TreeNode* bstToGst(TreeNode* root) {
        dfs(root,0);
        return root;
    }
*/
// 利用中序遍历的性质
/*
    int sum = 0;
    void dfs(TreeNode *root) {

        if(nullptr == root) {
            return;
        }
        dfs(root->right);

        sum += root->val;
        root->val = sum;

        dfs(root->left);
    }
    TreeNode* bstToGst(TreeNode* root) {
        dfs(root);
        return root;
    }
*/

// 收集树中金币
/*
class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& es) {

        int n = static_cast<int>(coins.size()); int rest = n;

        std::unordered_map<int, std::vector<int>> edges;
        std::vector<int> in(n,0);
        // 建图
        for(auto e : es) {

            int a = e[0];
            int b = e[1];
            edges[a].push_back(b); in[a]++;
            edges[b].push_back(a); in[b]++;
        }

        // 将没有金币的叶子结点入队
        std::queue<int> q;
        for(int i = 0; i < n; ++i) {
            if(in[i] == 1 && coins[i] == 0) {
                q.push(i);
            }
        }

        while(!q.empty()) {
            int hd = q.front();
            --in[hd];
            --rest;
            q.pop();
            for(auto e : edges[hd]) {
                if(--in[e] == 1 && coins[e] == 0) {
                    q.push(e);
                }
            }
        }

        for(int _ = 0; _ < 2; ++_) {

            for(int i = 0; i < n; ++i) {
                if(in[i] == 1) {
                    q.push(i);
                }
            }

            while(!q.empty()) {
                int hd = q.front();
                --in[hd];
                --rest;
                q.pop();
                for(int v: edges[hd]) {
                    --in[v];
                }
            }
        }
        return rest == 0 ? 0 : (rest - 1) * 2;
    }
};
*/

// 到达首都的最少油耗
/*
class Solution {
public:
    int seats = 0;
    long long ans = 0;
    std::unordered_map<int, std::vector<int>> edges;

    int dfs(int ch, int pa) {
        int sum = 1;
        for(auto e : edges[ch]) {

            if(e != pa) {
                int ret = dfs(e, ch);
                ans += (ret + seats - 1) / seats;
                sum += ret;
            }
        }
        return sum;
    }

    long long minimumFuelCost(vector<vector<int>>& roads, int _seats) {

        seats = _seats;
        for(auto e : roads) {

            edges[e[0]].push_back(e[1]);
            edges[e[1]].push_back(e[0]);
        }

        dfs(0, -1);
        return ans;
    }
};
*/

// 验证回文串II
/*
    bool validPalindrome(string s) {

        int n = static_cast<int>(s.size());
        int l = 0;
        int r = n - 1;

        auto func = [&](int low, int high) {
            while(low < high) {
                if(s[low] != s[high]) {
                    return false;
                }
                low++;
                high--;
            }
            return true;
        };

        while(l < r) {
            if(s[l] == s[r]) {
                l++; r--;
            } else {
                return func(l + 1, r) || func(l, r - 1);
            }
        }

        return true;
    }
*/

// 最小化旅行的价格总和
/*
class Solution
{
public:
    int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price, vector<vector<int>> &trips)
    {
        // 建图
        vector<vector<int>> adjTable(n);
        for (auto &edge : edges)
        {
            adjTable[edge[0]].push_back(edge[1]);
            adjTable[edge[1]].push_back(edge[0]);
        }

        // 统计每个点被访问的次数
        vector<int> visitCount(n, 0);

        // 对每个 trip 使用 dfs 找到最短路径
        for (auto &trip : trips)
        {
            stack<array<int, 2>> pathStack;
            vector<bool> visited(n, false);
            int start = trip[0];
            int end = trip[1];
            pathStack.push({start, 0});
            visited[start] = true;
            while (!pathStack.empty())
            {
                auto [curNode, nextNodeIndex] = pathStack.top();

                if (curNode == end) // 找到最短路径后更新 visitCount
                {
                    while (!pathStack.empty())
                    {
                        auto [node, _] = pathStack.top();
                        pathStack.pop();
                        ++visitCount[node];
                    }
                    break;
                }
                if (nextNodeIndex == adjTable[curNode].size())
                {
                    pathStack.pop();
                    continue;
                }

                int nextNode = adjTable[curNode][nextNodeIndex];
                ++pathStack.top()[1];
                if (!visited[nextNode])
                {
                    visited[nextNode] = true;
                    pathStack.push({nextNode, 0});
                }
            }
        }

        // 每个节点的总共 price
        vector<int> nodeTotalPrice(n);
        for (int i = 0; i < n; ++i)
        {
            nodeTotalPrice[i] = price[i] * visitCount[i];
        }

        // 建树
        vector<vector<int>> treeChildren(n);
        vector<int> treeParent(n, -1);
        queue<int> q;
        q.push(0); // 任选一个节点当作根
        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            for (int adjNode : adjTable[node])
            {
                if (adjNode != treeParent[node])
                {
                    treeChildren[node].push_back(adjNode);
                    q.push(adjNode);
                    treeParent[adjNode] = node;
                }
            }
        }

        // 在树上 dp
        // dp[0][node] 表示 node 不减半时, node 及其子树的最小 price
        // dp[1][node] 表示 node 减半时, node 及其子树的最小 price
        vector<vector<int>> dp(2, vector<int>(n, 0));

        // 维护叶子节点
        vector<int> unsolvedChildrenCount(n);
        unordered_set<int> toSolve;
        for (int i = 0; i < n; ++i)
        {
            int childrenCount = treeChildren[i].size();
            unsolvedChildrenCount[i] = childrenCount;
            if (childrenCount == 0)
            {
                toSolve.insert(i);
            }
        }

        while (!toSolve.empty())
        {
            // 维护新的叶子节点
            unordered_set<int> nextSolve;
            for (int node : toSolve)
            {
                dp[0][node] = nodeTotalPrice[node];
                dp[1][node] = nodeTotalPrice[node] / 2;

                for (int child : treeChildren[node])
                {
                    dp[0][node] += min(dp[0][child], dp[1][child]); // node不减半, 各个 child 可以选择是否减半
                    dp[1][node] += dp[0][child];                    // node减半, child 必须不减半
                }

                int parent = treeParent[node];
                if (parent == -1)
                {
                    return min(dp[0][0], dp[1][0]);
                }
                --unsolvedChildrenCount[parent];
                if (unsolvedChildrenCount[parent] == 0)
                {
                    nextSolve.insert(parent);
                }
            }
            toSolve.swap(nextSolve);
        }
        return -1;
    }
};
*/

// 重新规划路线
/*
class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        std::unordered_map<int, std::vector<int>> in;
        std::unordered_map<int, std::vector<int>> out;

        for(auto & v : connections) {
            out[v[0]].push_back(v[1]);
            in[v[1]].push_back(v[0]);
        }

        std::vector<bool> vis(n,false);
        std::queue<int> q;
        q.push(0);
        vis[0] = true;

        int ans = 0;
        while(!q.empty()) {

            auto hd = q.front(); q.pop();

            for(auto e : out[hd]) {

                if(!vis[e]) {
                    ans++;
                    q.push(e);
                    vis[e] = true;
                }
            }


            for(auto e : in[hd]) {

                if(!vis[e]) {
                    q.push(e);
                    vis[e] = true;
                }
            }
        }

        return ans;
    }
};
*/
/*
    std::unordered_map<int, std::vector<int>> in;
    std::unordered_map<int, std::vector<int>> out;
    int ans = 0;
    void dfs(int hd, std::vector<bool> &vis) {
        vis[hd] = true;
        for(auto e : out[hd]) {
            if(!vis[e]) {
                ans++;
                dfs(e,vis);
            }
        }
        for(auto e : in[hd]) {
            if(!vis[e]) {
                dfs(e,vis);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        for(auto & v : connections) {
            out[v[0]].push_back(v[1]);
            in[v[1]].push_back(v[0]);
        }
        std::vector<bool> vis(n,false);
        dfs(0,vis);
        return ans;
    }
*/

// 出租车的最大盈利
/*
  long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {

        std::vector<std::vector<std::pair<int, int>>> ends(n + 1);

        for(auto &v : rides) { // 记录每一个结束点有多少个开始点及对应的盈利
            ends[v[1]].push_back({v[0], v[1] - v[0] + v[2]});
        }

        std::vector<long long> dp(n + 1, 0);

        for(int i = 1; i <= n; ++i) {

            dp[i] = dp[i - 1]; // 表示没有开始点到达i所获得的利润
            for(auto [s, p] : ends[i]) {
                dp[i] = std::max(dp[i], dp[s] + p); // 更新到达结束点i所能获得的最大盈利
            }
        }

        return dp[n];
    }
*/
/*
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {

        int m = rides.size();
        std::sort(rides.begin(), rides.end());
        long long f[m]; std::memset(f, -1, sizeof(f));

        std::function<long long(int)> dfs = [&](int i) -> long long {
            if (i >= m) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }

            int st = rides[i][0], ed = rides[i][1], tip = rides[i][2];
            int pos = lower_bound(rides.begin() + i + 1, rides.end(), ed, [](auto& a, int val) { return a[0] < val; }) - rides.begin();
            return f[i] = max(dfs(i + 1), dfs(pos) + ed - st + tip);
        };
        return dfs(0);
    }
*/

// 下一个更大的数值平衡数
/*
class Solution {
public:
    int nextBeautifulNumber(int n) {

        for(int num = n + 1; ; ++num) {

            // std::unordered_map<int, int> count; // 统计每一个数位出现的个数
            int count[10] = { 0 };

            for(int tmp = num; tmp > 0; tmp /= 10) {
                count[tmp%10]++;
            }
            bool flag = true;
            // for(int tmp = num; tmp > 0; tmp /= 10) {
            //     if(tmp % 10 != count[tmp%10]) {
            //         flag = false;
            //         break;
            //     }
            // }
            // for(auto &[a, b] : count) {
            //     if(a != b) {
            //         flag = false;
            //         break;
            //     }
            // }
            for(int i = 0; i < 10; ++i) {
                if(count[i] != 0 && count[i] != i) {
                    flag = false;
                }
            }
            if(flag) {
                return num;
            }
        }

        return -1;
    }
};
*/

// 是否所有 1 都至少相隔 k 个元素
/*
bool kLengthApart(vector<int>& nums, int k) {

        while(!nums.empty()) {

            int back = nums.back();
            nums.pop_back();

            if(back == 1) {
                int c = 0;
                while(!nums.empty() && nums.back() == 0) {
                    nums.pop_back();
                    ++c;
                }
                if(c < k && !nums.empty()) {
                    return false;
                }
            }
        }

        return true;
    }
*/

// 爬楼梯
/*
    int climbStairs(int n) {
        std::vector<int> dp(n + 1, 0);
        dp[1] = 1;
        if(n >= 2) {
            dp[2] = 2;
        }
        for(int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
*/

// 二叉搜索子树的最大键值和
/*
// 暴力超时：
class Solution {
public:

    int sum = 0;
    int prev = INT_MIN;
    bool isBSTree(TreeNode* root) {

        // if (root == nullptr)
        //     return true;
        // if (!isBSTree(root->left) || root->val <= prev)
        //     return false;
        // prev = root->val;
        // sum += root->val;
        // return isBSTree(root->right);

        if (root == nullptr) {
            return true;
        }

        bool left = isBSTree(root->left);

        bool mid = true;
        if (prev != INT_MIN) {
            if (root->val <= prev) {
                mid = false;
            }
        }
        prev = root->val;
        sum += root->val;
        bool right = isBSTree(root->right);

        return left && right && mid;
    }

    int maxSumBST(TreeNode* root) {

        if (root == nullptr) {
            return 0;
        }
        int ans = 0;
        ans = maxSumBST(root->left);
        ans = std::max(maxSumBST(root->right), ans);

        sum = 0;
        prev = INT_MIN;
        if (isBSTree(root)) {
            ans = std::max(ans, sum);
        }
        return ans;
    }
};
*/
/*
class Solution {
public:
    int maxSumBST(TreeNode* root) {

        int ans = 0;
        std::function<std::tuple<bool,int,int,int>(TreeNode*)> dfs = [&](TreeNode *root){

            if(root == nullptr) {
                return std::make_tuple(true, INT_MAX, INT_MIN, 0);
            }

            auto [lb,lmin,lmax,lsum] = dfs(root->left);
            auto [rb,rmin,rmax,rsum] = dfs(root->right);
            int sum = lsum + rsum + root->val;
            if(lb && rb && lmax < root->val && root->val < rmin) {
                std::cout<<sum<<" ";
                ans = std::max(ans, sum);
                return std::make_tuple(true, std::min(root->val,lmin), std::max(root->val,rmax), sum);
            } else {

                return std::make_tuple(false,0,0,sum);
            }
        };
        dfs(root);
        return ans;
    }
};
*/

// 最小体力消耗路径
/*
class UnionFindSet
{
private:
    std::vector<int> _ufs;
public:
    UnionFindSet(size_t n)
        :_ufs(n,-1)
    {}

    bool Union(int x1, int x2) // 两个集合合并
    {
        int root1 = FindRootIndex(x1);
        int root2 = FindRootIndex(x2);

        if (root1 == root2) // 已经在一个集合，不需要合并
            return false;

        // x2合并到x1中
        this->_ufs[root1] += this->_ufs[root2];
        this->_ufs[root2] = root1;

        return true;
    }

    int FindRootIndex(int x) // 找根结点的下标
    {
        int root = x;
        while (this->_ufs[root] >= 0)
        {
            root = this->_ufs[root];
        }

        return root;
    }

    bool IsInSet(int x1, int x2) // 判断在不在一个集合
    {
        int root1 = FindRootIndex(x1);
        int root2 = FindRootIndex(x2);
        return root1 == root2;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {

        int nr = heights.size();
        int nc = heights.back().size();

        std::vector<std::vector<int>> edges;

        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {

                if(i + 1 < nr) {
                    edges.push_back({std::abs(heights[i + 1][j] - heights[i][j]), i * nc + j, (i + 1) * nc + j});
                }
                if(j + 1 < nc) {
                    edges.push_back({std::abs(heights[i][j + 1] - heights[i][j]), i * nc + j, i * nc + j + 1});
                }
            }
        }
        std::sort(edges.begin(), edges.end(),[](auto& a, auto& b){
            return a[0] < b[0];
        });

        UnionFindSet ufs(nr * nc);
        int ans = 0;
        for(auto & e : edges) {
            ans = e[0];
            ufs.Union(e[1],e[2]);
            if(ufs.IsInSet(0,nr * nc - 1)) {
                break;
            }
        }
        return ans;
    }
};
*/

/*
// class Solution {
// public:
//     // err:
//     vector<int> secondGreaterElement(vector<int>& nums) {

//         int n = static_cast<int>(nums.size());

//         vector<int> index;
//         for(int i = 0; i < n; ++i) {
//             index.push_back(i);
//         }


//         std::sort(index.begin(), index.end(),[&](const int &e1, const int &e2){
//             return nums[e1] < nums[e2];
//         });

//         for(auto e : index) {
//             std::cout<<e<<" ";
//         }
//         std::cout<<"\n";


//         std::vector<int> result;

//         for(int i = 0; i < n; ++i) {

//             int l = 0;
//             int r = n - 1;
//             while(l < r) { // 找右端点
//                 int mid = l + ((r - l + 1) >> 1);
//                 if(nums[index[mid]] <= nums[i]) {
//                     l = mid;
//                 } else {
//                     r = mid - 1;
//                 }
//             }

//             int count = 0;
//             for(int j = l + 1; j < n; ++j) {

//                 if(index[j] > i) {
//                     if(++count == 2) {
//                         result.push_back(nums[index[j]]);
//                     }
//                 }

//             }

//             std::cout<< l <<"\n";
//         }


//         return result;
//     }
// };

// // 0 2 4 6 9
// // 2 0 1 4 3
// 下一个更大元素 IV
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {

        int n = static_cast<int>(nums.size());
        std::vector<int> result(n, -1);

        if (n == 1) {
            return result;
        }
        vector<int> index;
        for(int i = 0; i < n; ++i) {
            index.push_back(i);
        }

        std::sort(index.begin(), index.end(),[&](const int &e1, const int &e2){
            return (nums[e1] < nums[e2]) || (nums[e1] == nums[e2] && e1 > e2);
        });


        std::set<int> tree;
        tree.insert(index[n - 1]);
        tree.insert(index[n - 2]);

        for(int i = n - 3; i >= 0; --i) {
            auto it = tree.lower_bound(index[i]);
            if(it != tree.end()) {
                std::cout<<*it<<"\n";
                ++it;
                if(it != tree.end()) {
                    result[index[i]] = nums[*it];
                }
            }
            tree.insert(index[i]);
        }

        return result;
    }
};
*/

// 字典序最小回文串
/*
string makeSmallestPalindrome(string s) {

        int l = 0; int r = static_cast<int>(s.size()) - 1;

        while(l < r) {

            if(s[l] != s[r]) {
                s[l] = s[r] = s[l] > s[r] ? s[r] : s[l];
            }
            l++;
            r--;
        }

        return s;
    }
*/

// 两个数对之间的最大乘积差
/*
    int maxProductDifference(vector<int>& nums) {
        std::set<int> tree;

        for(auto e : nums) {
            tree.insert(e);
        }

        auto it = tree.rbegin();
        int l = *it;
        ++it;
        l *= *it;

        auto rit = tree.begin();
        int r = *rit;
        ++rit;
        r *= *rit;

        return l - r;
    }
*/

// 交替打印字符串
/*
class FizzBuzz {
private:
    int i;
    int n;
    std::mutex lock;
    std::condition_variable cv;

public:
    FizzBuzz(int n) : i(1) {
        this->n = n;
    }

    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {

        std::unique_lock<std::mutex> ul(lock);

        while(i <= n) {

            if(i % 3 == 0 && i % 5 != 0) {
                printFizz();
                i++;
                cv.notify_all();
            }

            while(i <= n && !(i % 3 == 0 && i % 5 != 0)) {
                cv.wait(ul);
            }
        }

    }

    // printBuzz() outputs "buzz".
    void buzz(function<void()> printBuzz) {
        std::unique_lock<std::mutex> ul(lock);

        while(i <= n) {

            if(i % 3 != 0 && i % 5 == 0) {
                printBuzz();
                i++;
                cv.notify_all();
            }

            while(i <= n && !(i % 3 != 0 && i % 5 == 0)) {
                cv.wait(ul);
            }
        }
    }

    // printFizzBuzz() outputs "fizzbuzz".
    void fizzbuzz(function<void()> printFizzBuzz) {
        std::unique_lock<std::mutex> ul(lock);

        while(i <= n) {

            if(i % 3 == 0 && i % 5 == 0) {
                printFizzBuzz();
                i++;
                cv.notify_all();
            }

            while(i <= n && !(i % 3 == 0 && i % 5 == 0)) {
                cv.wait(ul);
            }
        }
    }

    // printNumber(x) outputs "x", where x is an integer.
    void number(function<void(int)> printNumber) {
        std::unique_lock<std::mutex> ul(lock);

        while(i <= n) {

            if(i % 3 != 0 && i % 5 != 0) {
                printNumber(i);
                i++;
                cv.notify_all();
            }

            while(i <= n && !(i % 3 != 0 && i % 5 != 0)) {
                cv.wait(ul);
            }
        }
    }
};
*/

// 航班预订统计
/*
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

        std::vector<int> difference(n + 1 + 1, 0);

        for(auto &v : bookings) {
            int first = v[0];
            int last = v[1];
            int seats = v[2];

            difference[first] += seats;
            difference[last + 1] -= seats;
        }

        std::vector<int> ans;
        ans.push_back(difference[1]);
        for(int i = 2; i <= n; ++i) {
            ans.push_back(ans.back() + difference[i]);
        }
        return ans;
    }
*/

// 用邮票贴满网格图
/*
class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int nr = grid.size(); int nc = grid.back().size();
        // 求二维前缀和
        std::vector<std::vector<int>> sums(nr + 1, std::vector<int>(nc + 1, 0));
        for(int i = 1; i <= nr; ++i) {
            for(int j = 1; j <= nc; ++j) {
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }
        // 求二维差分数组
        std::vector<std::vector<int>> diff(nr + 2, std::vector<int>(nc + 2, 0));
        for (int i2 = stampHeight; i2 <= nr; i2++) {
            for (int j2 = stampWidth; j2 <= nc; j2++) {
                int i1 = i2 - stampHeight + 1;
                int j1 = j2 - stampWidth + 1;
                if (sums[i2][j2] - sums[i2][j1 - 1] - sums[i1 - 1][j2] + sums[i1 - 1][j1 - 1] == 0) {
                    diff[i1][j1]++;
                    diff[i1][j2 + 1]--;
                    diff[i2 + 1][j1]--;
                    diff[i2 + 1][j2 + 1]++;
                }
            }
        }
        // 检查矩阵中是否存在值为0的点。如果存在，那么该点无法被邮票覆盖。
        for(int i = 1; i <= nr; ++i) {
            for(int j = 1; j <= nc; ++j) {
                diff[i][j] = diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1] + diff[i][j];
                if(grid[i - 1][j - 1] == 0 && diff[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
};
*/

// 反转二叉树的奇数层
/*
    TreeNode* reverseOddLevels(TreeNode* root) {

        std::queue<TreeNode *> q1;
        std::queue<TreeNode *> q2;

        q1.push(root);
        q2.push(root);

        std::stack<int> st;
        int level = 0;
        while(!q1.empty()) {
            int n = q1.size();

            for(int i = 0; i < n; ++i) {
                auto hd = q1.front(); q1.pop();
                st.push(hd->val);
                if(hd->left != nullptr) {
                    q1.push(hd->left);
                    q1.push(hd->right);
                }
            }

            for(int i = 0; i < n; ++i) {
                auto hd = q2.front(); q2.pop();
                if(level % 2 == 1) {
                    hd->val = st.top();
                }
                st.pop();
                if(hd->left != nullptr) {
                    q2.push(hd->left);
                    q2.push(hd->right);
                }
            }
            level++;
        }
        return root;
    }
*/
/*
class Solution {
private:
    void dfs(TreeNode* node1, TreeNode* node2, bool isSwap){
        if(nullptr == node1) {
            return;
        }
        if(isSwap){
            swap(node1->val, node2->val);   // 需要交换值，交换
        }
        dfs(node1->left, node2->right, !isSwap);     // node1的左子节点和node2的右子节点是一对 // 因为只翻转奇数层，因此标志位交替变化
        dfs(node1->right, node2->left, !isSwap);     // node1的右子节点和node2的左子节点是一对
    }
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        // 从根节点的左右子节点开始递归，左右子节点是第一层，奇数次，需要翻转
        dfs(root->left, root->right, true);
        return root;
    }
};
*/

// 统计区间中的整数数目 done
/*
class CountIntervals {
    typedef pair<int, int> pii;

    int ans = 0;
    set<pii> st;

public:
    CountIntervals() {
    }

    void add(int left, int right) {
        int L = left, R = right;
        // 这里 (R1, L1) >= (R2, L2)，若 R1 > R2 或 R1 = R2 且 L1 >= L2
        auto it = st.lower_bound(pii(left - 1, -2e9));
        while (it != st.end()) {
            if (it->second > right + 1) break;
            L = min(L, it->second);
            R = max(R, it->first);
            ans -= it->first - it->second + 1;
            st.erase(it++);
        }
        ans += R - L + 1;
        st.insert(pii(R, L));
    }

    int count() {
        return ans;
    }
};
*/

// 使用最小花费爬楼梯 
/*
class Solution
{
public:
    // 解法二:
    // 状态表示dp[i]: dp[i]表示从i位置到达楼顶的最小代价
    // 状态转移方程: dp[i]=std::min( dp[i+1]+cost[i], dp[i+2]+cost[i] );
    // 初始化dp[n-1]=cost[n-1],dp[n-2]=cost[n-2]
    // 遍历顺序: 从右到左
    // 返回结果: dp[0]
    int minCostClimbingStairs(vector<int>& cost)
    {
        // 边界处理
        if(cost.size()==1)
            return cost[0];
        if(cost.size()==2)
            return std::min(cost[0],cost[1]);

        int n=static_cast<int>(cost.size());

        std::vector<int> dp(n,0);
        dp[n-1]=cost[n-1];
        dp[n-2]=cost[n-2];

        for(int i=n-3;i>=0;--i)
        {
            dp[i]=std::min( dp[i+1]+cost[i], dp[i+2]+cost[i] );
        }

        return std::min(dp[0],dp[1]);
    }
};
*/
/*
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int size = cost.size();
        vector<int> minCost(size);
        minCost[0] = 0;
        minCost[1] = min(cost[0], cost[1]);
        for (int i = 2; i < size; i++) {
            minCost[i] = min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);
        }
        return minCost[size - 1];
    }
};
*/

// 两个数对之间的最大乘积差
/*
class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        std::multiset<int> tree;

        for(auto e : nums) {
            tree.insert(e);
        }

        auto it = tree.rbegin();
        int l = *it;
        ++it;
        l *= *it;

        auto rit = tree.begin();
        int r = *rit;
        ++rit;
        r *= *rit;

        return l - r;
    }
};
*/
/*
class Solution
{
public:
    int maxProductDifference(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int a = nums[0],        b = nums[1];
        int c = nums[n-2],      d = nums[n-1];
        return c * d - a * b;
    }
};
*/

// 寻找峰值
/*
    int findPeakElement(vector<int>& nums) {

        int n = static_cast<int>(nums.size());
        for(int i = 0; i < n; ++i) {
            bool flag = true;
            if(i - 1 >= 0) {
                if(nums[i - 1] > nums[i]) {
                    flag = false;
                }
            }
            if(i + 1 < n) {
                if(nums[i + 1] > nums[i]) {
                    flag = false;
                }
            }
            if(flag) {
                return i;
            }
        }
        return -1;
    }
*/
/*
class Solution {
public:
    int findPeakElement(vector<int>& nums)
    {
        int left = 0;
        int right = static_cast<int>(nums.size() - 1);

        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid]<nums[mid+1])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }

        return left;
    }
};
*/

// 旋转字符串
/*
    bool rotateString(string s, string goal) {
        if(s.size() != goal.size()) {
            return false;
        }

        std::string str = s;
        str += s;

        auto pos = str.find(goal);
        if(pos != std::string::npos) {
            return true;
        }
        return false;
    }
*/

// 寻找峰值 II
/*
    vector<int> findPeakGrid(vector<vector<int>>& mat) {

        int n = static_cast<int>(mat.size());

        auto getMaxIndex = [](std::vector<int> &v)->int{
            return max_element(v.begin(), v.end()) - v.begin();
        };

        int l = 0; int r = n - 1;

        while(l < r) {
            int mid = l + ((r - l) >> 1);
            int maxi = getMaxIndex(mat[mid]);
            if(mat[mid][maxi] > mat[mid + 1][maxi]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return {l, getMaxIndex(mat[l])};
    }
*/
/*
// class Solution {
// public:
//     // err: 必须找出行或者列的最大值而非极值
//     vector<int> findPeakGrid(vector<vector<int>>& mat) {

//         int nr = static_cast<int>(mat.size());
//         int nc = static_cast<int>(mat.back().size());

//         for(int i = 0; i < nr; ++i) {
//             auto &v = mat[i];
//             int l = 0; int r = static_cast<int>(v.size()) - 1;
//             while(l < r) {
//                 int mid = l + ((r - l) >> 1);
//                 if(v[mid] < v[mid + 1]) {
//                     l = mid + 1;
//                 } else {
//                     r = mid;
//                 }
//             }
//             int flag = true;
//             if(i - 1 >= 0) {
//                 if(mat[i - 1][l] > mat[i][l]) {
//                     flag = false;
//                 }
//             }
//             if(i + 1 < nr) {
//                 if(mat[i + 1][l] > mat[i][l]) {
//                     flag = false;
//                 }
//             }

//             if(flag) {
//                 return {i, l};
//             }
//         }

//         for(int i = 0; i < nr; ++i) {
//             int l = 0; int r = nr - 1;
//             while(l < r) {
//                 int mid = l + ((r - l) >> 1);
//                 if(mat[mid][i] < mat[mid + 1][i]) {
//                     l = mid + 1;
//                 } else {
//                     r = mid;
//                 }
//             }

//             int flag = true;
//             if(i - 1 >= 0) {
//                 if(mat[l][i - 1] > mat[l][i - 1]) {
//                     flag = false;
//                 }
//             }
//             if(i + 1 < nc) {
//                 if(mat[l][i + 1] > mat[l][i + 1]) {
//                     flag = false;
//                 }
//             }

//             if(flag) {
//                 return {i, l};
//             }
//         }

//         return {};
//     }
// };
*/

// 判别首字母缩略词
/*
class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        if(words.size() != s.size()) {
            return false;
        }

        int pos = 0;
        for(auto &str : words) {
            if(str.front() != s[pos++]) {
                return false;
            }
        }

        return pos == s.size();
    }
};
*/

// 括号生成
/*
class Solution
{
public:
    // 什么是一个有效的括号组合
    //      1.左括号数==右括号数
    //      2.从0下标开始的任意子串必须左括号数>=右括号数

    std::vector<std::string> result;
    std::string path;
    int left,right,n;

    vector<string> generateParenthesis(int _n)
    {
        left=right=0;
        n=_n;
        dfs();
        return result;
    }

    void dfs()
    {
        // 当右括号数等于n时则表示生成有效的括号组合完成
        if(right==n)
        {
            result.push_back(path);
            return;
        }

        if(left<n) // 保证左括号数小于等于n
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back();
            left--;
        }

        if(left>right) // 保证从0下标开始的任意子串始终左括号数>=右括号数
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }

};
*/

// 美丽塔 II
/*
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        //单调栈并记录
        int n=maxHeights.size();
        vector<long long> left(n),right(n);

        vector<int> s;
        s.push_back(-1);

        //左遍历单调
        for(int i=0;i<n;++i){

            while(s.back()!=-1&&maxHeights[s.back()]>maxHeights[i]){
                s.pop_back();
            }

            long long sum=(long long)maxHeights[i]*(i-s.back());

            if(s.back()!=-1) {
                sum+=left[s.back()];
            }
            left[i]=sum;
            s.push_back(i);
        }

        //右遍历单调
        s.clear();
        s.push_back(n);

        for(int i=n-1;i>=0;--i){

            while(s.back()!=n&&maxHeights[s.back()]>maxHeights[i]){
                s.pop_back();
            }

            long long sum=(long long)maxHeights[i]*(s.back()-i);

            if(s.back()!=n) {
                sum+=right[s.back()];
            }
            right[i]=sum;
            s.push_back(i);
        }

        long long ans=0;
        for(int i=0;i<n;++i){

            ans=max(ans,right[i]+left[i]-maxHeights[i]);
        }
        return ans;
    }
};
*/

// 得到山形数组的最少删除次数
/*
class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> dpL(n, 1);  // 以i结尾的最长递增子序列的长度
        vector<int> dpR(n, 1);  // 以i开始的最长递增子序列的长度

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dpL[i] = max(dpL[i], dpL[j] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j > i; --j) {
                if (nums[i] > nums[j]) {
                    dpR[i] = max(dpR[i], dpR[j] + 1);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (dpL[i] > 1 && dpR[i] > 1) {
                ans = max(ans, dpL[i] + dpR[i] - 1);
            }
        }

        return n - ans;
    }
};
*/

// 移除石子使总数最小
/*
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        std::priority_queue<int> p(piles.begin(),piles.end());
        int sum = std::accumulate(piles.begin(),piles.end(),0);
        for(int i = 0;i < k;++i)
        {
            int top = p.top();
            p.pop();
            sum -= top/2;
            top -= top/2;
            p.push(top);
        }
        return sum;
    }
};
*/
/*
三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。
P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;
P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。
要求用伪代码描述。
*/
/*
//semaphore space = N;
//semaphore odd = 0;
//semaphore even = 0;
//
//void P1() {
//    int num = produce();
//    wait(space);
//    put(num);
//
//    if(num % 2 == 0) {
//        signal(even);
//    } else {
//        signal(odd);
//    }
//}
//
//void P2() {
//    wait(odd);
//    int num = getodd();
//    countodd();
//    signal(space);
//}
//
//void P3() {
//    wait(even);
//    int num = geteven();
//    counteven();
//    signal(space);
//}

const int N;
semaphore lockCon = 1; // 消费者互斥访问缓冲区
semaphore lockPro = 1; // 生产者互斥访问缓冲区
int buffer[N]; // 缓冲区

semaphore spaceCount = N;
semaphore dataCount = 0;

int indexPro = 0; // 生产者对应的下标
int indexCon = 0; // 消费者对应的下标
semaphore oddCount = 0;
semaphore evenCount = 0;

void Producer() {
     while(true) {
        int num = produce(); // 获取正整数

        wait(spaceCount); // 判断是否还有空间存放num
        wait(lockPro);

        buffer[indexPro] = num; // 存放num
        indexPro = (indexPro + 1) % N;

        signal(lockPro);
        signal(dataCount);
     }
}

void Consumer() {

    while(true) {

        wait(dateCount);
        wait(lockCon);
        int num = buffer[indexCon];
        indexCon = (indexCon + 1) % N;
        signal(lockCon);
        signal(spaceCount);
        if(num % 2 == 0) {
            signal(evenCount);
        } else {
            signal(oddCount);
        }
        consume(num);
    }
}
*/
/*
某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号,等待叫号。
取号机每次仅允许一位顾客使用。当营业员空闲时,通过叫号选取一位顾客,并为其服务。顾客和营业员的活动过程描述如下:
int empty_seat = 10;
semaphore mutex = 1; // 互斥访问empty_seat变量
semaphore client= 0;
semaphore ready = 0;

process 顾客i
{
    P(mutex);
    if(empty_seat > 0) {
        empty_seat--;
        V(mutex);
        V(client);
        从取号机获取一个号码;
        P(ready);
        等待叫号;
        获取服务;
    } else {
        V(mutex);
    }
}

process 营业员
{
    while(true) {
        P(client);
        V(ready);
        叫号;
        P(mutex);
        empty_seat++;
        V(mutex);
        为顾客服务;
    }
}
*/

// 收集足够苹果的最小花园周长
/*
// class Solution {
// public:
//     long long minimumPerimeter(long long neededApples) {
//         long long n = cbrt(neededApples / 4.0);
//         if (2 * n * (n + 1) * (2 * n + 1) < neededApples) {
//             n++;
//         }
//         return 8 * n;
//     }
// };
class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long i = 1;
        while(neededApples > 0){
            neededApples -= 12 * (i * i);
            i++;
        }
        return 8 * (i - 1);
    }
};
*/

// 托普利茨矩阵
/*
// class Solution {
// public:
//     bool isToeplitzMatrix(vector<vector<int>>& matrix) {
//         int m = matrix.size(), n = matrix[0].size();
//         for (int i = 1; i < m; i++) {
//             for (int j = 1; j < n; j++) {
//                 if (matrix[i][j] != matrix[i - 1][j - 1]) {
//                     return false;
//                 }
//             }
//         }
//         return true;
//     }
// };
// class Solution {
// public:
//     bool isToeplitzMatrix(vector<vector<int>>& matrix) {
//         for (int i = 0; i < matrix.size() - 1; ++i) {
//             for (int j = 0; j < matrix[0].size() - 1; ++j) {
//                 if (matrix[i][j] != matrix[i + 1][j + 1])
//                     return false;
//             }
//         }
//         return true;
//     }
// };
// class Solution
// {
// public:
//     bool isToeplitzMatrix(vector<vector<int>>& matrix)
//     {
//         int R = matrix.size(), C = matrix[0].size();
//         unordered_map<int, int> rc_diff;
//         for (int r = 0; r < R; r ++)
//         {
//             for (int c = 0; c < C; c ++)
//             {
//                 if (rc_diff.count(r - c) == 0)
//                     rc_diff[r - c] = matrix[r][c];
//                 else
//                     if (rc_diff[r - c] != matrix[r][c])
//                         return false;
//             }
//         }
//         return true;
//     }
// };
*/

// 不浪费原料的汉堡制作方案
/*
class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < cheeseSlices * 2 || cheeseSlices * 4 < tomatoSlices) {
            return {};
        }
        return {tomatoSlices / 2 - cheeseSlices, cheeseSlices * 2 - tomatoSlices / 2};
    }
};
*/

// 所有子字符串美丽值之和
/*
class Solution {
public:
    int beautySum(string s) {
        int n = s.size();
        int sum = 0;
        for(int i = 0; i < n; ++i) {
            std::vector<int> count(26, 0);
            int maxcnt = INT_MIN;
            for(int j = i; j < n; ++j) {
                int c = ++count[s[j] - 'a'];
                if(c > maxcnt) {
                    maxcnt = c;
                }
                int mincnt = INT_MAX;
                for(auto e : count) {

                    if(e != 0 && e < mincnt) {
                        mincnt = e;
                    }
                }
                sum += (maxcnt - mincnt);
            }
            //std::cout<<maxcnt - mincnt<<"\n";
        }
        return sum;
    }
};
*/

// 倍数求和
/*
class Solution {
public:
    int sumOfMultiples(int n) {
        int sum = 0;
        for(int i = 1; i <= n; ++i) {
            if(i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
};
*/

// 构建字典序最大的可行序列
/*
class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        visited.resize(n+1,false);
        res.resize(2*(n-1)+1,0);
        back_track(0);
        return res;
    }

    vector<int> res;
    vector<bool> visited;

    bool back_track(int pos) {
        int n=visited.size()-1;
        if (pos>=res.size())    return true;
        if (res[pos]!=0)    return back_track(pos+1);
        for (int i=n;i>=1;i--) {
            if (visited[i]) continue;
            if (i==1)   {
                visited[1]=true;
                res[pos] = 1;
                if (back_track(pos+1))  return true;
                visited[1]=false;
                res[pos] = 0;
                return false;
            }
            else {
                if (pos+i>=res.size())  continue;
                if (res[pos+i]!=0)  continue;
                res[pos]=i;res[pos+i]=i;
                visited[i] = true;
                if (back_track(pos+1))  return true;
                res[pos]=0;res[pos+i]=0;
                visited[i] = false;
            }
        }
        return false;
    }
};
*/

// 保龄球游戏的获胜者
/*
class Solution {
public:
    int isWinner(vector<int>& player1, vector<int>& player2) {

        int score1 = 0;
        int score2 = 0;
        int n = static_cast<int>(player1.size());

        for(int i = 0; i < n; ++i) {
            score1 += player1[i];
            score2 += player2[i];

            if((i - 1 >= 0 && player1[i - 1] == 10) || (i - 2 >= 0 && player1[i - 2] == 10)) {
                score1 += player1[i];
            }
            if((i - 1 >= 0 && player2[i - 1] == 10) || (i - 2 >= 0 && player2[i - 2] == 10)) {
                score2 += player2[i];
            }
        }

        if(score1 > score2 ) {
            return 1;
        } else if(score1 < score2) {
            return 2;
        } else {
            return 0;
        }
    }
};
*/

// 矩阵对角线元素的和
/*
class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size(); int sum = 0;
        for(int i = 0; i < n; ++i) {
            sum += (mat[i][i] + mat[i][n - i - 1]);
        }

        if(n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        return sum;
    }
};
*/
/*
class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size(), sum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || i + j == n - 1) {
                    sum += mat[i][j];
                }
            }
        }
        return sum;
    }
};
*/

// Excel 表列序号
/*
class Solution {
public:
    int titleToNumber(string columnTitle) {
        int ans = 0; int k = 0;
        int n = static_cast<int>(columnTitle.size());
        for(int i = n - 1; i >= 0; --i) {
            ans += (std::pow(26,k++)) * (columnTitle[i] - 'A' + 1);
        }
        return ans;
    }
};
*/

// 最大二叉树
/*
class Solution {
public:
    TreeNode * create(vector<int> &nums, int l, int r) {
        if(l > r) {
            return nullptr;
        }
        int maxval = nums[l];
        int pos = l;
        for(int i = l; i <= r; ++i) {
            // maxval = std::max(maxval, nums[i]);
            if(maxval < nums[i]) {
                maxval = nums[i];
                pos = i;
            }
        }
        TreeNode *node = new TreeNode(maxval);
        node->left = create(nums, l, pos - 1);
        node->right = create(nums, pos + 1, r);
        return node;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return create(nums,0,nums.size() - 1);
    }
};
*/

// 购买两块巧克力
/*
    int buyChoco(vector<int>& prices, int money) {
        std::sort(prices.begin(),prices.end());
        return prices[0] + prices[1] > money ? money : money - prices[0] - prices[1];
    }
    int buyChoco(vector<int>& prices, int money) {
        int fi = INT_MAX, se = INT_MAX;
        for (auto p : prices) {
            if (p < fi) {
                se = fi;
                fi = p;
            } else if (p < se) {
                se = p;
            }
        }
        return money < fi + se ? money : money - fi - se;
    }
*/

// 三数之和
/*
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() < 3) {
            return {};
        }
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> result;
        for(int i = 0; i < nums.size() - 2; ++i) {

            if(i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }

            int l = i + 1;
            int r = nums.size() - 1;

            while(l < r) {
                if(nums[i] + nums[l] + nums[r] == 0) {
                    result.push_back({nums[i],nums[l],nums[r]});
                    l++;
                    while(l < r && nums[l - 1] == nums[l]) {
                        l++;
                    }
                    r--;
                    while(l < r && nums[r + 1] == nums[r]) {
                        r--;
                    }

                } else if(nums[i] + nums[l] + nums[r] > 0){
                    r--;
                } else {
                    l++;
                }
            }
        }
        return result;
    }
};
*/

// 一周中的第几天
/*
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> week = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
        vector<int> monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};

        int days = 365 * (year - 1971) + (year - 1969) / 4;

        for (int i = 0; i < month - 1; ++i) {
            days += monthDays[i];
        }
        if ((year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) && month >= 3) {
            days += 1;
        }

        days += day;
        return week[(days + 3) % 7];
    }
};
*/

// 统计参与通信的服务器
/*
class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int nr = grid.size(), nc = grid[0].size();
        vector<int> rows(nr), cols(nc);

        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j]) {
                    ++rows[i];
                    ++cols[j];
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};
*/

// 一年中的第几天
/*
class Solution {
public:
    int dayOfYear(string date) {
        int y = atoi(date.substr(0,4).c_str());
        int m = atoi(date.substr(5,2).c_str());
        int d = atoi(date.substr(8,2).c_str());
        int days[] {31,28,31,30,31,30,31,31,30,31,30,31};
        for(int i = 0; i < m - 1; ++i) {
            d += days[i];
            if(i == 1 && ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0))) {
                d += 1;
            }
        }
        return d;
    }
};
*/

// 盛最多水的容器
/*
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        ans = 0
        while l < r:
            area = min(height[l],height[r]) * (r - l)
            ans = max(ans,area)
            if(height[l] < height[r]):
                l += 1
            else:
                r -= 1
        return ans
*/

// 接雨水
/*
class Solution {
public:
    int trap(vector<int>& height) {
        int n = static_cast<int>(height.size());
        std::vector<int> premax(n,0); premax[0] = height[0];
        auto sufmax = premax;   sufmax[n - 1] = height[n - 1];
        // 求i位置的最大前缀值和最大后缀值
        for(int i = 1; i < n; ++i) {
            premax[i] = std::max(premax[i - 1], height[i]);
        }
        for(int i = n - 2; i >= 0; --i) {
            sufmax[i] = std::max(sufmax[i + 1], height[i]);
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            ans += (std::min(premax[i], sufmax[i]) - height[i]);
        }
        return ans;
    }
};
*/
/*
class Solution {
public:
    int trap(vector<int>& height) {
        int n = static_cast<int>(height.size());
        int l = 0; int r = n - 1;
        int pre = height[0];
        int suf = height[n - 1];
        int ans = 0;
        while(l < r) {
            pre = std::max(pre,height[l]);
            suf = std::max(suf,height[r]);
            // 先计算低的一侧
            if(pre < suf) {
                ans += (pre - height[l]);
                l++;
            } else {
                ans += (suf - height[r]);
                r--;
            }
        }
        return ans;
    }
};
*/

// 替换子串得到平衡字符串
/*
class Solution {
public:
    bool check(std::unordered_map<char, int> &cnt, int k) {
        if(cnt['Q'] > k || cnt['W'] > k || cnt['E'] > k || cnt['R'] > k) {
            return false;
        }
        return true;
    }

    int balancedString(string s) {

        std::unordered_map<char, int> cnt;
        for(auto ch : s) {
            cnt[ch]++;
        }

        int n = static_cast<int>(s.size());
        int k = n / 4;

        if(check(cnt, k)) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int ans = n;
        for(int l = 0, r = 0; l < n; l++) {

            while(r < n && !check(cnt, k)) {
                cnt[s[r++]]--;
            }

            if (!check(cnt, k)) {
                break;
            }

            ans = std::min(ans, r - l);
            cnt[s[l]]++;
        }
        return ans;
    }
};
*/

// 完全二叉树插入器
/*
class CBTInserter {
private:
    std::vector<int> arr;
public:
    CBTInserter(TreeNode* root) {
        if(root != nullptr) {
            std::queue<TreeNode *> q;
            q.push(root);

            while(!q.empty()) {
                auto hd = q.front(); q.pop();
                arr.push_back(hd->val);
                if(hd->left != nullptr) {
                    q.push(hd->left);
                }
                if(hd->right != nullptr) {
                    q.push(hd->right);
                }
            }
        }
    }

    int insert(int v) {
        int pos = static_cast<int>(arr.size());
        arr.push_back(v);
        return arr[(pos - 1)/2]; // 类似堆的下标映射
    }

    TreeNode* get_root() {

        TreeNode *root = new TreeNode(arr.front());
        std::queue<TreeNode *> q;
        q.push(root);
        int i = 1;

        while(i < arr.size()) {

            auto hd = q.front(); q.pop();

            hd->left = new TreeNode(arr[i++]);
            q.push(hd->left);

            if(i < arr.size()) {
                 hd->right = new TreeNode(arr[i++]);
                q.push(hd->right);
            }
        }
        return root;
    }
};
*/

// 从链表中移除节点
/*
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        auto curr = head;
        std::vector<decltype(head)> st;
        while(curr != nullptr) {
            while(!st.empty() && st.back()->val < curr->val) {
                st.pop_back();
            }
            st.push_back(curr);
            curr = curr->next;
        }
        ListNode * res = nullptr;
        while(!st.empty()) {
            auto node = st.back(); st.pop_back();
            node->next = res;
            res = node;
            // if(res == nullptr) {
            //     res = node;
            // } else {
            //     node->next = res;
            //     res = node;
            // }
        }
        return res;
    }
};
*/

// 二叉树展开为链表
/*
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> l;
        preorderTraversal(root, l);
        int n = l.size();
        for (int i = 1; i < n; i++) {
            TreeNode *prev = l.at(i - 1), *curr = l.at(i);
            prev->left = nullptr;
            prev->right = curr;
        }
    }

    void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {
        if (root != NULL) {
            l.push_back(root);
            preorderTraversal(root->left, l);
            preorderTraversal(root->right, l);
        }
    }
};
*/

// 被列覆盖的最多行数
/*
class Solution {
public:
    int check(int num) { // 统计1的个数
        int count = 0;
        for(int i = 0; i < 31; ++i) {
            if(((num >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }

    int maximumRows(vector<vector<int>>& matrix, int numSelect) {

        int nr = static_cast<int>(matrix.size());
        int nc = static_cast<int>(matrix.back().size());
        std::vector<int> mask(nr, 0);
        for(int i = 0; i < nr; ++i) {

            for(int j = 0; j < nc; ++j) {
                if(matrix[i][j] == 1) {
                    mask[i] |= (1 << j);
                }
            }
        }

        // 枚举所有列的情况
        int num = 0; int limit = (1 << nc);
        int ans = 0;
        while(++num < limit) {
            if(check(num) != numSelect) {
                continue;
            }
            int tmp = 0;
            for(int i = 0; i < nr; ++i) {
                // 等于自身表示该行被覆盖
                if((mask[i] & num) == mask[i]) {
                    tmp++;
                }
            }
            ans = std::max(tmp, ans);
        }
        return ans;
    }
};
*/

// 队列中可以看到的人数
/*
class Solution {
public:
    // 暴力
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = static_cast<int>(heights.size());
        std::vector<int> ans;
        for(int i = 0; i < n; ++i) {
            int c = 0;
            int t = 0;
            for(int j = i + 1; j < n; ++j) {
                if(t < heights[j]) {
                    c++;
                }
                t = std::max(heights[j], t);
                if(t >= heights[i]) {
                    break;
                }
            }
            ans.push_back(c);
        }
        return ans;
    }
*/
/*
class Solution {
public:
    // 单调栈
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n);
        stack<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && st.top() < heights[i]) {
                st.pop();
                ans[i]++;
            }
            if (!st.empty()) { // 还可以再看到一个人
                ans[i]++;
            }
            st.push(heights[i]);
        }
        return ans;
    }
};

*/

// 在链表中插入最大公约数
/*
 ListNode* insertGreatestCommonDivisors(ListNode* head) {
        auto cur = head;
        decltype(cur) pre = nullptr;
        while(cur != nullptr) {

            if(pre != nullptr) {
                int ret = __gcd(pre->val, cur->val);
                auto node = new ListNode(ret);
                pre->next = node;
                node->next = cur;
            }
            pre = cur;
            cur = cur->next;
        }
        return head;
    }
*/
/*
#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "请输入两个整数: ";
    cin >> a >> b;
    cout << "最大公约数为: " << gcd(a, b) << endl;

    return 0;
}
*/

//  赎金信
/*
// class Solution {
// public:
//     bool canConstruct(string ransomNote, string magazine) {
//         if (ransomNote.size() > magazine.size()) {
//             return false;
//         }
//         vector<int> cnt(26);
//         for (auto & c : magazine) {
//             cnt[c - 'a']++;
//         }
//         for (auto & c : ransomNote) {
//             cnt[c - 'a']--;
//             if (cnt[c - 'a'] < 0) {
//                 return false;
//             }
//         }
//         return true;
//     }
// };
class Solution {
public:
    bool canConstruct(string a, string b) {
        int n=a.size(), m=b.size();
        std::vector<int> s1(30),s2(30);
        for(int i=0;i<n;i++)
            s1[a[i]-'a']++;

        for(int i=0;i<m;i++)
            s2[b[i]-'a']++;
        for(int i=0;i<26;i++)
            if(s1[i]>s2[i]) return 0;
        return 1;
    }
};
*/

// 求一个整数的惩罚数
/*
class Solution {
public:
    bool check(const std::string &str, int pos, int s, int t) {
        if(str.size() == pos) {
            return s == t;
        }
        int n = str.size();
        int sum = 0;
        for(int i = pos; i < n; ++i) {
            sum = sum * 10 + (str[i] - '0');
            if(sum + s > t) {
                break;
            }
            if(check(str, i + 1, sum + s, t)) {
                return true;
            }
        }
        return false;
    }

    int punishmentNumber(int n) {
        int sum = 0;
        for(int i = 1; i <= n; ++i) {

            std::string str = std::to_string(i * i);
            if(check(str, 0, 0, i)) {
                sum += i * i;
            }
        }
        return sum;
    }
};
*/

// 回旋镖的数量
/*
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>> &points) {
        int ans = 0;

        unordered_map<int, int> cnt;

        for (auto &p : points) {
            cnt.clear();

            for (auto &q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                ++cnt[dis];
            }

            for (auto &[_, c] : cnt) {
                ans += c * (c - 1);
            }
        }
        return ans;
    }
};
*/

// 字符串中的额外字符
/*
class Solution {
public:
    // 状态表示dp[i]: 表示n位置之前的最小额外字符数
    // 状态转移方程: 不以s[i]为结尾和以s[i]结尾
    //  dp[i] =  min(dp[i - 1] + 1, min(dp[j]))
    // 初始化: dp[0] = 1
    // 遍历顺序: 从左到右
    // 返回结果: dp[n]
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = static_cast<int>(s.size());

        std::unordered_set<std::string> hash;
        for (auto str : dictionary) {
            hash.insert(str);
        }
        std::vector<int> dp(n + 1, INT_MAX);

        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = i - 1; j >= 0; j--) {
                if (hash.find(s.substr(j, i - j)) != hash.end()) {
                    dp[i] = min(dp[i], dp[j]);
                }
            }
        }
        return dp[n];
    }
};
*/

// 删除子串后的字符串最小长度
/*
class Solution {
public:
    int minLength(string s) {
        std::stack<char> st;
        for(auto ch : s) {

            if(!st.empty()) {

                if(st.top() == 'A' && ch == 'B') {
                    st.pop();
                    continue;
                }
                if(st.top() == 'C' && ch == 'D') {
                    st.pop();
                    continue;
                }
            }
            st.push(ch);
        }
        return st.size();
    }
};
*/

// 字符串中最大的 3 位相同数字
/*
class Solution {
public:
    string largestGoodInteger(string num) {
        std::string str;
        int n = static_cast<int>(num.size());

        for(int i = 2; i < n; ++i) {
            if(num[i - 2] == num[i - 1] && num[i - 1] == num[i]) {
                if(str.empty() || str[0] < num[i]) {
                    str.clear();
                    str.append(3, num[i]);
                }
            }
        }
        return str;
    }
};
*/

// 构造有效字符串的最少插入数
/*
class Solution {
public:
    int addMinimum(string word) {
        int n = word.size(), cnt = 1;
        for (int i = 1; i < n; i++) {
            if (word[i] <= word[i - 1]) {
                cnt++;
            }
        }
        return cnt * 3 - n;
    }
};
*/

/*
class Solution {
public:
    int addMinimum(string word) {
        int n = word.size();
        int res = word[0] - word[n - 1] + 2;
        for (int i = 1; i < n; i++) {
            res += (word[i] - word[i - 1] + 2) % 3;
        }
        return res;
    }
};
*/

// 统计出现过一次的公共字符串
/*
class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {

        std::unordered_map<std::string, int> hash1;
        std::unordered_map<std::string, int> hash2;

        for(auto &str : words1) {
            hash1[str]++;
        }
        for(auto &str : words2) {
            hash2[str]++;
        }

        int ans = 0;
        for(auto &str : words1) {
            if(hash1[str] == 1 && hash2[str] == 1) {
                ans++;
            }
        }

        return ans;
    }
};
*/

// 环和杆  
/*
    int countPoints(string rings) {
        int n = static_cast<int>(rings.size());
        std::unordered_map<char, std::set<char>> hash;

        for(int i = 0; i < n; ++i) {
            if(i & 1) {
                hash[rings[i]].insert(rings[i - 1]);
            }
        }

        int count = 0;
        for(auto &[_, s] : hash) {
            if(s.size() == 3) {
                count++;
            }
        }

        return count;
    }
*/

// 改造限制重复的字符串
/*
class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        std::map<int, int, std::greater<int>> dict;
        for(auto & ch : s) {
            dict[ch - 'a']++;
        }

        std::string ans;

        auto it = dict.begin();
        while(it != dict.end()) {

            int c = repeatLimit;
            while(c--) {
                ans.push_back(it->first + 'a');
                if(--it->second == 0) {
                    break;
                }
            }

            if(it->second != 0) {
                auto tmp = it++;
                while(it != dict.end() && it->second <= 0) {
                    it++;
                }
                if(it == dict.end()) {
                    return ans;
                }
                ans.push_back(it->first + 'a');
                it->second--;
                it = tmp;
            } else {
                while(it != dict.end() && it->second <= 0) {
                    it++;
                }
            }
        }

        return ans;
    }
};
*/

// 删除排序链表中的重复元素
/*
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }

        return head;
    }
};

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == nullptr) {
           return head;
        }

        while (head.next != null && head.next.val == head.val) {
            head.next = head.next.next;
        }

        head.next = deleteDuplicates(head.next);

        return head;
   }
}
*/

// 删除排序链表中的重复元素 II
/*
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* pre = head;
        ListNode* cur = head->next;

        ListNode* ret = nullptr;
        ListNode* tail = nullptr;

        while (cur != nullptr) {

            if (pre->val != cur->val) {

                if (ret == nullptr) {
                    ret = tail = pre;
                }
                else {
                    tail->next = pre;
                    tail = pre;
                }
                pre = cur;
                cur = cur->next;
            }
            else {

                int val = cur->val;
                while (cur != nullptr) {
                    if (cur->val == val) {
                        cur = cur->next;
                    }
                    else {
                        break;
                    }
                }

                if (cur == nullptr || cur->next == nullptr) {
                    if (tail != nullptr) {
                        tail->next = cur;
                    }
                    else {
                        ret = tail = cur;
                    }
                    return ret;
                }
                else {
                    pre = cur;
                    cur = cur->next;
                }
            }
        }
        pre->next == nullptr;
        tail->next = pre;
        return ret;
    }
};
*/
/*
ListNode* deleteDuplicates(ListNode* head) {

        std::unordered_map<int,int> hash;

        ListNode *curr=head;

        while(curr!=nullptr)
        {
            hash[curr->val]++;
            curr=curr->next;
        }

        ListNode *newhead=nullptr, *tail=nullptr;
        curr=head;
        while(curr!=nullptr)
        {
            ListNode *next=curr->next;
            curr->next=nullptr;

            if(hash[curr->val]==1)
            {
                if(newhead==nullptr)
                {
                    newhead=tail=curr;
                }
                else
                {
                    tail->next=curr;
                    tail=curr;
                }
            }
            curr=next;
        }
        return newhead;
    }
*/

// 打家劫舍
/*
class Solution {
public:

    std::vector<int> memo;

    int dfs(const vector<int>& nums, int pos) {
        if(pos < 0) {
            return 0;
        }
        if(memo[pos] != -1) {
            return memo[pos];
        }
        int ret = std::max(dfs(nums, pos - 2) + nums[pos], dfs(nums, pos - 1));
        memo[pos] = ret;

        return ret;
    }

    int rob(vector<int>& nums) {
        memo.resize(410, -1);
        return dfs(nums, nums.size() - 1);
    }
};
*/
/*
class Solution {
public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        vector<int> f(n + 2);
        for (int i = 0; i < n; ++i)
            f[i + 2] = max(f[i + 1], f[i] + nums[i]);
        return f.back();
    }
};
*/

// 最大字符串配对数目
/*
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {

        std::unordered_map<std::string, int> hash;
        for(auto &str : words) {
            hash[str]++;
        }
        int ans = 0;
        for(auto &str : words) {

            if(hash[str] == 1){

                hash[str]++;
                std::reverse(str.begin(), str.end());
                if(hash[str] == 1) {
                    ans++;
                    hash[str]++;
                }
            }
        }
        return ans;
    }
};
*/
/*
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        int n = words.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (words[i][0] == words[j][1] && words[i][1] == words[j][0]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};
*/

// 拿出最少数目的魔法豆
/*
    long long minimumRemoval(vector<int>& beans) {
        int n = static_cast<int>(beans.size());

        long long sum = 0;
        for(int i = 0; i < n; ++i) {
            sum += beans[i];
        }

        std::sort(beans.begin(), beans.end());
        long long res = 0; // 表示剩余豆子的个数
        for(int i = 0; i < n; ++i) {
            res = std::max(res, ((long long)beans[i] * (n - i)));
        }

        return sum - res;
    }
*/

// 奖励最顶尖的 K 名学生
/*
class Solution {
public:
    vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {

        // 对正面及负面单词进行hash便于快速查找
        std::unordered_set<std::string> pe;
        for(auto &str : positive_feedback) {
            pe.insert(str);
        }
        std::unordered_set<std::string> ne(negative_feedback.begin(), negative_feedback.end());

        int n = static_cast<int>(student_id.size());
        // 获取评语中的单词
        auto split = [](std::string &str, std::vector<std::string> & words){

            int begin = 0;
            int end = 0;
            int n = static_cast<int>(str.size());
            while(end < n) {

                while(end < n && str[end] != ' ') {
                    end++;
                }
                words.push_back(str.substr(begin, end - begin));
                begin = end + 1;
                end++;
            }
        };

        // 对同学进行评分
        std::vector<int> scores(n, 0);
        for(int i = 0; i < n; ++i) {

            std::vector<std::string> words;
            split(report[i], words);

            for(auto & word : words) {
                if(pe.find(word) != pe.end()) {
                    scores[i] += 3;
                }
                if(ne.find(word) != ne.end()) {
                    scores[i] -= 1;
                }

                // std::cout<< word << "\n";
            }
        }

        // id -- index
        std::unordered_map<int, int> index;
        for(int i = 0; i < n; ++i) {
            index[student_id[i]] = i;
        }
        std::sort(student_id.begin(), student_id.end(), [&](const int &e1, const int & e2){
            // return scores[index[e1]] > scores[index[e2]] ? scores[index[e1]] > scores[index[e2]] : e2 > e1;
            if(scores[index[e1]] == scores[index[e2]]) {
                return e1 < e2;
            } else {
                return scores[index[e1]] > scores[index[e2]];
            }
        });

        // 返回结果
        auto result = scores; result.clear();
        for(int i = 0; i < k; ++i) {
            result.push_back(student_id[i]);
        }
        return result;
    }
};
*/

// 按分隔符拆分字符串
/*
class Solution {
public:
    vector<string> splitWordsBySeparator(vector<string>& words, char separator) {

        auto split = [](std::string &str, char separator, std::vector<std::string> &result){
            int begin = 0;
            int end = 0;
            int n = static_cast<int>(str.size());

            while(!str.empty() && str.back() == separator) {
                str.pop_back();
            }
            if(str.empty()) {
                return;
            }

            while(end < n) {
                while(begin < n && str[begin] == separator) {
                    begin++;
                }
                end = begin;
                while(end < n && str[end] != separator) {
                    end++;
                }
                result.push_back(str.substr(begin, end - begin));
                // std::cout<< result.back()<<std::endl;
                begin = end + 1;
                end++;
            }
        };

        std::vector<std::string> result;
        for(auto &str : words) {
            split(str, separator, result);
        }

        return result;
    }
};
*/
/*
class Solution {
public:
    vector<string> splitWordsBySeparator(vector<string>& words, char separator) {
        vector<string> ans;
        for (const auto& w : words) {
            istringstream ss(w);
            string s;
            while (getline(ss, s, separator)) {
                if (!s.empty()) {
                    ans.push_back(s);
                }
            }
        }
        return ans;
    }
};
*/

// 重复的DNA序列
/*
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        std::unordered_map<std::string, int> hash;
        std::vector<std::string> result;

        int l = 0;
        int r = 9;
        int n = static_cast<int>(s.size());

        while(r < n) {
            std::string sub = s.substr(l, r - l + 1);
            if(++hash[sub] == 2) {
                result.push_back(sub);
            }

            l++;
            r++;
        }

        return result;
    }
};
*/

// 执行 K 次操作后的最大分数
/*
class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> q(nums.begin(), nums.end());
        long long ans = 0;
        while(k--) {
            int x = q.top();
            q.pop();
            ans += x;
            q.push((x + 2) / 3);
        }
        return ans;
    }
};
*/

// 最长替换子数组
/*
class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int i = 1;
        int ans = -1;
        int n = static_cast<int>(nums.size());

        while(i < n) {
            if(nums[i] - nums[i - 1] != 1) {
                i++;
                continue;
            }

            int m = 1;
            int pos = i;
            int len = (pos - i + 1);

            while(pos < n && nums[pos] - nums[pos - 1] == m) {
                m = -m;
                pos++;
                len++;
                ans = std::max(ans, len);
            }
            i++;
        }
        return ans;
    }
};
*/

// 美丽塔 I
/*
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = static_cast<int>(maxHeights.size());

        long long ans = 0;
        for(int i = 0; i < n; ++i) {
            long long s = maxHeights[i];

            long long m = maxHeights[i];
            for(int j = i - 1; j >= 0; --j) {
                m = std::min(m, (long long)maxHeights[j]);
                s += m;
            }

            m = maxHeights[i];
            for(int k = i + 1; k < n; ++k) {
                m = std::min(m, (long long)maxHeights[k]);
                s += m;
            }
            ans = std::max(ans, s);
        }
        return ans;
    }
};
*/

// 计算 K 置位下标对应元素的和
/*
class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {

        int ans = 0;

        for(int i = 0; i < nums.size(); ++i) {

            auto func = [&]() {

                int c = 0;
                for(int j = 0; j < 32; ++j) {
                    if(((i >> j) & 1) == 1) {
                        c++;
                    }
                }
                return c == k;
            };

            if(func()) {
                ans += nums[i];
            }
        }
        return ans;
    }
};
*/

// 二叉搜索树中的众数
/*
class Solution {
public:
    std::vector<int> result;
    int val = INT_MAX;
    int mc = INT_MIN;
    int c = 0;
    void dfs(TreeNode *root) {
        if(root == nullptr) {
            return;
        }
        dfs(root->left);

        if(root->val == val) {
            c++;
        } else {
            c = 1;
            val = root->val;
        }

        if(c == mc) {
            result.push_back(val);
        } else if(c > mc){
            mc = c;
            result = {val};
        }

        dfs(root->right);
    }

    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return result;
    }
};
*/

// 路径总和 III
/*
class Solution {
public:
    int ans = 0;
    void dfs(TreeNode *root, long long sum, int target) {

        if(nullptr == root) {
            return;
        }

        int val = root->val;
        if(val + sum == target) {
            ans++;
        }

        dfs(root->left, val + sum, target);
        dfs(root->right, val + sum, target);
    }

    int pathSum(TreeNode* root, int targetSum) {
        if(nullptr == root) {
            return 0;
        }

        dfs(root, 0, targetSum);
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);
        return ans;
    }
};
*/
/*
class Solution {
public:
    std::unordered_map<long long, int> hash;

    int dfs(TreeNode *root, long long sum, int target) {
        if(nullptr == root) {
            return 0;
        }

        sum += root->val;
        int count = 0;
        // if(hash.find(sum - target) != hash.end()) {
            count += hash[sum - target];
        // }

        hash[sum]++;
        count += dfs(root->left, sum, target);
        count += dfs(root->right, sum, target);
        hash[sum]--;
        return count;
    }

    int pathSum(TreeNode* root, int targetSum) {
        hash[0LL] = 1;
        return dfs(root, 0, targetSum);
    }
};
*/

// 美化数组的最少删除数
/*
class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int res = 0;
        int len = 0;
        for (int i = 0; i < nums.size() - 1; i++){
            // 删除元素
            if (len % 2 == 0 && nums[i] == nums[i+1]){
                res++;
                len--;
            }
            len++;
        }
        len++;
        // 处理数组长度为奇数
        if (len % 2 != 0) {
            res++;
        }
        return res;
    }
};
*/
/*
class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == nums[i + 1]) {
                ++ans;
            } else {
                ++i;
            }
        }
        ans += (n - ans) % 2;
        return ans;
    }
};
*/

// 种花问题
/*
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int c) {

        int n = static_cast<int>(flowerbed.size());

        for(int i = 0; i < n; ++i) {
            if(flowerbed[i] == 0) {

                if(i - 1 >= 0 && flowerbed[i - 1] == 1) {
                    continue;
                }
                if(i + 1 < n && flowerbed[i + 1] == 1) {
                    continue;
                }
                flowerbed[i] = 1;
                c--;

                std::cout<<c<<"\n";
            }
        }
        return c <= 0;
    }
};
*/

// 找出不同元素数目差数组
/*
class Solution {
public:
    vector<int> distinctDifferenceArray(vector<int>& nums) {
        int n = static_cast<int>(nums.size());

        std::unordered_set<int> hash;
        std::vector<int> sufC(n, 0);

        for(int i = n - 2; i >= 0; --i) {
            if(hash.find(nums[i + 1]) != hash.end()) {

                sufC[i] = sufC[i + 1];
            } else {

                sufC[i] = sufC[i + 1] + 1;
                hash.insert(nums[i + 1]);
            }
        }

        int preC = 0;
        hash.clear();
        std::vector<int> result;

        for(int i = 0; i < n; ++i) {
            if(hash.find(nums[i]) == hash.end()) {

                preC++;
                hash.insert(nums[i]);
            }
            result.push_back(preC - sufC[i]);
        }
        return result;
    }
};
*/

// 三角形最小路径和
/*
class Solution {
public:
    // 状态表示dp[i][j]: 表示从三角形顶点到该位置的最小路径和
    // 状态转移方程: dp[i][j] = min( dp[i-1][j-1], dp[i-1][j] ) + t[i][j]
    // 初始化: dp[0][0] = t[0][0]
    // 遍历顺序: 从左到右从上到下
    // 返回结果: min(dp[n - 1])
    int minimumTotal(vector<vector<int>>& triangle) {

        int n = static_cast<int>(triangle.size());
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < triangle[i].size() - 1; ++j) {
                dp[i][j] = dp[i - 1][j] + triangle[i][j];
                // 当j == 0时
                if(j - 1 >= 0) {
                    dp[i][j] = std::min(dp[i][j], dp[i - 1][j - 1] + triangle[i][j]);
                }
            }
            // j == i 时
            dp[i][triangle[i].size() - 1] = dp[i - 1][triangle[i].size() - 2] + triangle[i][triangle[i].size() - 1];
        }

        return *std::min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
};
*/